AlgoVerse

Iterative inorder and preorder

Traverse a binary tree with an explicit stack instead of recursion: the same orders, but the stack that recursion hides is in plain view.

A recursive traversal really uses the call stack. Keep the stack ourselves and no recursion is needed, and the stack is in plain view.

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

A seven-node search tree; inorder 3 6 7 15 17 18 20 (sorted) and preorder 15 6 3 7 18 17 20.

  1. class Node:
  2. def __init__(self, key):
  3. self.key = key
  4. self.left = None
  5. self.right = None
  8. def iterative(root):
  9. stack = []
  10. on_stack = [] # the keys of the nodes on the stack, for the picture
  11. # Inorder: go left as far as possible, pushing each node; then pop, visit, and go right.
  12. ino = []
  13. out = ino
  14. node = root
  15. while node is not None or stack:
  16. if node is not None:
  17. stack.append(node)
  18. on_stack.append(node.key)
  19. node = node.left
  20. else:
  21. node = stack.pop()
  22. on_stack.pop()
  23. ino.append(node.key)
  24. node = node.right
  25. # Preorder: pop and visit; push the right child first so the left one comes out first.
  26. pre = []
  27. out = pre
  28. if root is not None:
  29. stack.append(root)
  30. on_stack.append(root.key)
  31. while stack:
  32. node = stack.pop()
  33. on_stack.pop()
  34. pre.append(node.key)
  35. if node.right is not None:
  36. stack.append(node.right)
  37. on_stack.append(node.right.key)
  38. if node.left is not None:
  39. stack.append(node.left)
  40. on_stack.append(node.left.key)
  41. return ino, pre

Invariant: In inorder, the stack holds exactly the nodes whose left subtree is being traversed and that are not yet visited themselves.

Start

36715171820
on_stack—
ino—
pre—

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. iterative()line 8
Step 1 of 145
Black = visit_in, visit_pre · Orange = key steppush: 0/13 · visit_in: 0/7 · start_pre: 0/1 · visit_pre: 0/7
    Explanation

    The idea

    A recursive traversal really uses the call stack. Keep the stack ourselves and no recursion is needed, and the stack is in plain view.

    • Inorder: go left as far as possible, pushing each node. On reaching null, pop one, visit it and go to its right subtree.
    • Preorder: push the root; repeatedly pop one, visit it, and push its right child and then its left one, so the left comes out first.

    Cost

    Each node is pushed once and popped once: Θ(n). The stack grows to at most the tree's height h.

    What to watch in the trace

    • on_stack is the stack's keys (the bottom on the left). Compare the left and the right chain.