Iterative Tree Traversal

AQA 4.3.2 — Iterative tree traversal

Retrieval: Sequence 12 implemented pre-order, in-order and post-order traversal recursively. The previous lesson used an explicit stack for DFS as an alternative to recursion. This lesson combines both: the exact same traversal orders, but with the call stack made fully explicit, using a real stack data structure.

Key vocabulary

• Iterative traversal — a traversal implemented using an explicit loop and stack, rather than recursive function calls.
• Call stack — the implicit stack Python itself maintains for recursive calls (Sequence 10); an iterative traversal replaces it with a stack the programmer controls directly.

Understand — why go iterative at all?

Recursion is often the more readable choice, but it has a genuine limitation: every recursive call adds a frame to Python's call stack (Sequence 10), and Python enforces a maximum recursion depth. For a very deep, unbalanced tree (imagine one built by inserting already-sorted data into a BST, Sequence 12's degenerate-tree case), a recursive traversal could hit that limit and crash. An iterative traversal, using an explicit stack the programmer manages directly, has no such built-in limit.

See it — iterative pre-order

def iterative_preorder(root):
    if root is None:
        return []
    stack = [root]
    result = []
    while stack:
        node = stack.pop()
        result.append(node.value)
        if node.right:
            stack.append(node.right)   # pushed first...
        if node.left:
            stack.append(node.left)    # ...so this comes out first
    return result

See it — iterative in-order

def iterative_inorder(root):
    stack = []
    current = root
    result = []
    while stack or current:
        while current:
            stack.append(current)
            current = current.left
        current = stack.pop()
        result.append(current.value)
        current = current.right
    return result

Trace it — iterative pre-order on Sequence 12's tree

Reusing the exact 9-node tree from Sequence 12 (root 8; left subtree 3, 1, 6, 4, 7; right subtree 10, 14, 13):

Final: 8, 3, 1, 6, 4, 7, 10, 14, 13 — identical to Sequence 12's recursive pre-order result.

Reason about correctness — why "push right, then left" reproduces pre-order exactly

A stack is LIFO — the last item pushed is the first item popped. Pre-order requires visiting the node, then its entire left subtree, then its entire right subtree. By pushing the right child before the left child, the left child ends up on top of the stack, so it's popped — and therefore explored — before the right child, exactly matching pre-order's required sequence, entirely because of how LIFO ordering reverses the push order back into the correct visit order.

Debug it — diagnose, explain, fix, test, justify (wrong traversal order)

def iterative_preorder(root):
    if root is None:
        return []
    stack = [root]
    result = []
    while stack:
        node = stack.pop()
        result.append(node.value)
        if node.left:
            stack.append(node.left)    # pushed first...
        if node.right:
            stack.append(node.right)   # ...so RIGHT comes out first
    return result

This runs without any error at all, producing 8, 10, 14, 13, 3, 6, 7, 4, 1 instead of the correct pre-order sequence — the right subtree is explored entirely before the left.

1. Diagnose: which child ends up on top of the stack — and therefore gets popped first — when left is pushed before right?
2. Explain: using the LIFO reasoning above, why does pushing left before right cause right to be visited first?
3. Fix: swap the push order back to right-then-left.
4. Test: confirm the corrected version matches Sequence 12's recursive pre-order result exactly.
5. Justify: explain why this bug produces a complete, valid-looking list of every value — just in the wrong order — making it easy to miss without checking against a known-correct traversal.

(Pushing left before right puts right on TOP of the stack, so right is popped - and visited - first, producing a right-to-left traversal instead of pre-order's required left-to-right. The fix restores the right-then-left push order. This is dangerous because the output still contains all 9 values with no crash - only a careful order check catches it, exactly like Sequence 12's own in-order debug task.)

Common mistake

Assuming iterative traversal is always "better" than recursive simply because it avoids a recursion-depth risk. For a small or reasonably balanced tree, recursive traversal is often more readable and the depth risk never materialises — the choice, like every choice this course has covered, depends on the actual scenario.

Analyse — recursive vs. iterative

Both approaches are O(n) time (every node visited exactly once) and O(h) space in the worst case (h = tree height), whether that space is Python's own call stack (recursive) or an explicit stack (iterative). The genuine difference is robustness: recursion risks Python's built-in recursion-depth limit on a very deep, unbalanced tree; an explicit stack has no such fixed limit (only the machine's actual available memory).

Compare, select, justify

A system processes an extremely unbalanced binary search tree with 100,000 nodes, built by inserting already-sorted data (Sequence 12's degenerate case). Explain why an iterative traversal might be preferred here over a recursive one.

(An unbalanced tree built from sorted insertions has height close to 100,000 - a recursive traversal would need roughly 100,000 nested calls, risking Python's built-in recursion-depth limit and crashing with a RecursionError. An iterative traversal, using an explicit stack with no such built-in limit, avoids this risk entirely.)

Challenge

Adapt iterative_preorder into an iterative_postorder function (hint: post-order is notably trickier iteratively than pre-order or in-order — research one standard approach, such as using two stacks, and explain in your own words why it's needed).

Looking ahead: the next lesson applies this exact explicit-stack mechanism to a completely different problem — evaluating mathematical expressions written in postfix notation.