AlgoVerse

Tree traversals

Preorder, inorder and postorder traversal of a binary tree with recursion; inorder on a search tree gives the keys sorted.

Traversing a tree means visiting every node exactly once. In a binary tree, each node has a left and a right subtree, so recursion is the natural way: to traverse a tree, visit the root and traverse the two subtrees the same way. The three classic traversals differ only in where the root is visited:

Read the full explanation ↓
Input:
n=7PDF export

An uneven seven-node search tree; the three traversals give three different orders, and inorder is sorted.

  1. class Node:
  2. def __init__(self, key):
  3. self.key = key
  4. self.left = None
  5. self.right = None
  8. def traversals(root):
  9. pre = []
  10. preorder(root, pre)
  11. ino = []
  12. inorder(root, ino)
  13. post = []
  14. postorder(root, post)
  15. return pre, ino, post
  18. def preorder(node, out):
  19. if node is None:
  20. return
  21. out.append(node.key)
  22. preorder(node.left, out)
  23. preorder(node.right, out)
  26. def inorder(node, out):
  27. if node is None:
  28. return
  29. inorder(node.left, out)
  30. out.append(node.key)
  31. inorder(node.right, out)
  34. def postorder(node, out):
  35. if node is None:
  36. return
  37. postorder(node.left, out)
  38. postorder(node.right, out)
  39. out.append(node.key)

Invariant: Each call traverses the whole subtree rooted at node, and only then returns.

Start

36715171820

Recursion tree

Filled orange = running call · Orange outline = still on the stack · Grey = finished

Local variables

Orange = changed in this step

root object

  • key = 15
  • left = Node(key=6, left=Node(key=3, left=None, right=None), right=Node(key=7, left=None, right=None))
  • right = Node(key=18, left=Node(key=17, left=None, right=None), right=Node(key=20, left=None, right=None))

Call stack

  1. traversals()line 8
Step 1 of 185
Black = done_pre, done_in, done_post · Orange = key stepvisit: 0/21 · done_pre: 0/1 · done_in: 0/1 · done_post: 0/1

    How the work grows with input size

    Average of 8 random graphs per n (fixed seeds). Hollow marker = the input on screen.

    • visit
    • current input (n=7)
    02040603579111315n = number of keysvisit
    Show as a table
    nvisit
    39
    515
    721
    927
    1133
    1339
    1545
    Explanation

    The idea

    Traversing a tree means visiting every node exactly once. In a binary tree, each node has a left and a right subtree, so recursion is the natural way: to traverse a tree, visit the root and traverse the two subtrees the same way. The three classic traversals differ only in where the root is visited:

    | Traversal | Order | | --- | --- | | Preorder | node, left, right | | Inorder | left, node, right | | Postorder | left, right, node |

    The key fact: inorder on a search tree

    In a binary search tree, every key in the left subtree is smaller and every key in the right subtree is larger. So an inorder traversal gives the keys in ascending order.

    Uses

    • Preorder: copying a tree, writing an expression in Polish notation.
    • Postorder: deleting a tree, evaluating an expression tree, computing sizes or heights.

    Cost

    Every node is visited once: O(n). The recursion is as deep as the tree is high: log n for a balanced tree, n for a chain.

    What to watch in the trace

    • The orange node is node in the running call, and black nodes have already been added to the output.
    • The out list under the tree shows the order of visits.
    • In the "recursion tree", the ∅ calls are the missing children that return at once.
    • The "every loop round" detail level shows only the end of each of the three traversals.