5.3 Tree Traversals: Recursion, Stacks, and Queues

Prerequisites: Binary Tree Basics, Stack, and Queue, approximately 35 minutes. This lesson converts access timing into pre-order, in-order, and post-order traversals, then compares the state maintained by recursive call stacks, explicit stacks, and level-order queues.

After a Fork, Order Is Up to You

Arrays define order by index, linked lists by next node pointer. Trees may leave two unexplored branches at a single node. A traversal algorithm must answer two questions:

1. In what order are the left and right subtrees processed?
2. When is the current node added to the result?

This page uses the following example:

              1
            /   \
           2     3
          / \     \
         4   5     6

Three Timing Points for Depth-First Traversal

After entering a node in a recursive function, the execution passes through three distinct positions:

Position A: Before processing the left subtree
Position B: Between completion of the left subtree and start of the right subtree
Position C: After both left and right subtrees have been fully processed

Placing the "record current key" action at positions A, B, or C yields preorder, inorder, and postorder traversals respectively.

Traversal	Order	Sample Result	Common Use Cases
Preorder	Root, Left, Right	[1, 2, 4, 5, 3, 6]	Parent node processed before children; copying or serialization with null markers
Inorder	Left, Root, Right	[4, 2, 5, 1, 3, 6]	Sorted keys in a BST; ordinary binary trees do not guarantee ordering
Postorder	Left, Right, Root	[4, 5, 2, 6, 3, 1]	Child results processed before parent; computing directory sizes, evaluating expression trees

Preorder values alone cannot reconstruct the tree: [1, 2] does not say whether node 2 is a left or right child. Serialization also needs null-link markers distinguishable from ordinary values.

Complete Recursive and Iterative Implementations

All functions return a new list, with [] for an empty tree. Inputs must have no cycles or shared children. Iterative postorder uses (node, expanded) to choose what to do when a node is popped again: schedule its children first, then return to output the node. This avoids repeatedly inserting at the result list’s head.

from collections import deque

class TreeNode:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

def build_sample_tree():
    root = TreeNode(1)
    root.left = TreeNode(2)
    root.right = TreeNode(3)
    root.left.left = TreeNode(4)
    root.left.right = TreeNode(5)
    root.right.right = TreeNode(6)
    return root

def preorder_recursive(root):
    result = []

    def visit(node):
        if node is None:
            return
        result.append(node.value)
        visit(node.left)
        visit(node.right)

    visit(root)
    return result

def inorder_recursive(root):
    result = []

    def visit(node):
        if node is None:
            return
        visit(node.left)
        result.append(node.value)
        visit(node.right)

    visit(root)
    return result

def postorder_recursive(root):
    result = []

    def visit(node):
        if node is None:
            return
        visit(node.left)
        visit(node.right)
        result.append(node.value)

    visit(root)
    return result

def preorder_iterative(root):
    if root is None:
        return []

    result = []
    stack = [root]
    while stack:
        node = stack.pop()
        result.append(node.value)
        if node.right is not None:
            stack.append(node.right)
        if node.left is not None:
            stack.append(node.left)
    return result

def inorder_iterative(root):
    result = []
    stack = []
    current = root

    while current is not None or stack:
        while current is not None:
            stack.append(current)
            current = current.left
        current = stack.pop()
        result.append(current.value)
        current = current.right
    return result

def postorder_iterative(root):
    if root is None:
        return []

    result = []
    stack = [(root, False)]
    while stack:
        node, expanded = stack.pop()
        if expanded:
            result.append(node.value)
            continue

        stack.append((node, True))
        if node.right is not None:
            stack.append((node.right, False))
        if node.left is not None:
            stack.append((node.left, False))
    return result

def level_order(root):
    if root is None:
        return []

    result = []
    queue = deque([root])
    while queue:
        node = queue.popleft()
        result.append(node.value)
        if node.left is not None:
            queue.append(node.left)
        if node.right is not None:
            queue.append(node.right)
    return result

def level_order_by_level(root):
    if root is None:
        return []

    levels = []
    queue = deque([root])
    while queue:
        level = []
        for _ in range(len(queue)):
            node = queue.popleft()
            level.append(node.value)
            if node.left is not None:
                queue.append(node.left)
            if node.right is not None:
                queue.append(node.right)
        levels.append(level)
    return levels

sample = build_sample_tree()
pre = [1, 2, 4, 5, 3, 6]
ino = [4, 2, 5, 1, 3, 6]
post = [4, 5, 2, 6, 3, 1]
assert preorder_recursive(sample) == pre
assert preorder_iterative(sample) == pre
assert inorder_recursive(sample) == ino
assert inorder_iterative(sample) == ino
assert postorder_recursive(sample) == post
assert postorder_iterative(sample) == post
assert level_order(sample) == [1, 2, 3, 4, 5, 6]
assert level_order_by_level(sample) == [[1], [2, 3], [4, 5, 6]]

Trace Iterative Inorder

The traversal order is left, root, right. The algorithm first pushes the path from root to the leftmost node onto the stack:

Action	current	Stack (bottom → top)	Result
Initial	1	[]	[]
Pushed 1	2	[1]	[]
Pushed 2	4	[1, 2]	[]
Pushed 4	None	[1, 2, 4]	[]
Pop 4	None	[1, 2]	[4]
Pop 2	5	[1]	[4, 2]
Push and then pop 5	None	[1]	[4, 2, 5]

The stack holds nodes not yet output, waiting for a return visit. Some left subtrees are still being processed; others have just finished. After popping the node, turn to its right subtree, and the loop can reuse the same rule.

Why push right child first in preorder

Stack follows last-in-first-out. Preorder requires visiting the left child first, so the iteration code pushes the right child first, then the left:

push(right)
push(left)
pop() first gets left

The stack push order must follow the stack pop direction to achieve the desired traversal sequence.

Why Postorder Requires State

When you first encounter node 1, you can't immediately output it because nodes 2 and 3 haven't been processed yet. Iterative code pushes (1, True) back onto the stack, signaling "come back and output node 1 after its children are fully processed." Then it pushes the right and left children onto the stack, ensuring the left subtree is executed first.

A common alternative approach generates root, right, left, then reverses the entire sequence. This also produces postorder. result.reverse() reverses the list in place with constant auxiliary space; result[::-1] creates another Θ(n)-sized list. Repeatedly using insert(0, value) on a Python list for a single shift operation may end up being O(n) moves, potentially turning a simple traversal into O(n²).

Breadth-First and Layered Boundaries

Breadth-first traversal uses a queue. When processing a node, its children are added to the rear of the queue; nodes that entered earlier (and are thus at shallower levels) are processed first.

Grouped breadth-first traversal records len(queue) at the start of each round. This value represents the number of nodes remaining to be processed at the current level. The loop exactly extracts these nodes, and the children added to the queue are reserved for the next iteration.

Time and Auxiliary Space

Let n count nodes, h count height in edges, and w be maximum level width. The table covers nonempty trees; returning from an empty tree takes constant time and space:

Traversal	Time	Peak Auxiliary Space	What Determines the Peak
Recursive DFS	O(n)	O(h + 1)	The root-to-current-node path on the call stack
Iterative DFS	O(n)	O(h + 1)	The explicit stack containing pending ancestors or branches
Level-order BFS	O(n)	O(w)	The nodes of adjacent levels in the queue

The general upper bound O(w) can be written as O(n), but w better reflects actual space usage. In a chain-like tree, w = 1 is small; in a tree with a broad base, many nodes are stored simultaneously in the BFS queue.

O(h+1) is a general upper bound, not a tight bound for every shape. This page’s iterative preorder keeps at most one stack entry on a chain, while postorder with return markers retains ancestor state on the same chain.

The returned list itself requires Θ(n) space. The "auxiliary space" in complexity tables typically does not include space required by the caller for output; when analyzing, it's important to clarify whether the output is included.

Recursive Depth Is Not a Cross-Language Constant

Old code often states, "recursion overflows at depth 1000." That resembles some CPython default configurations, but is not an algorithmic or Java guarantee.

• Python uses sys.getrecursionlimit() to query the current interpreter's limit. This limit protects the C stack and does not imply that arbitrary recursion depths can be safely increased.
• In Java, recursion depth is influenced by thread stack size, frame size, JVM configuration, and the underlying platform. There is no fixed rule of 1000 levels.
• The C++ standard also does not specify a maximum recursion depth.

When handling potentially malicious deep trees, chained structures, or inputs of unknown scale, explicit stack usage provides better control over failure behavior. Balanced data structures inherently limit h at the source.

Java Container Correspondence

When implementing DFS stack logic in new Java code, use Deque<TreeNode> stack = new ArrayDeque<>(); and invoke push, pop, and peek. Oracle describes ArrayDeque as likely faster than the older Stack for this use; it is not a performance guarantee for every workload.

BFS can also use ArrayDeque<TreeNode> by calling offer and poll. This chapter focuses on public APIs and algorithm state, without relying on the node layout defined by LinkedList.

Common Errors

Recursive function reuses default list

def inorder(node, result=[]) causes multiple calls to share the same list. Each public call should create a new result.

Pre-order stack push order is reversed

Pushing left first, then right, results in popping the right child first. The output becomes root, right, left instead of root, left, right.

In-order visit timing is premature

Adding a node to the result as soon as it's entered produces pre-order traversal. In-order traversal requires visiting the left subtree first, then the current node.

Post-order only stores nodes, not phases

This implementation must record its return phase; outputting a node on its first pop would be premature. Other designs can use a last-visited reference, a reversed result, or a second stack. Each needs a clear account of its saved state.

Level-order mixes the next level into the current level

When grouping output, the current queue length must be saved before enqueueing children. Do not let the loop boundary grow with each enqueue operation.

Applying BST conclusions to general trees

The in-order traversal of the example tree is not sorted. Only when the BST global invariant holds does in-order traversal produce key-ordered output.

Debugging Order

1. First, write assertions for empty trees and single-node cases.
2. Manually compute the expected output lists for sample trees, covering four scenarios.
3. Compare the outputs of the recursive and iterative implementations one by one.
4. Print the contents of the stack or queue in logs, don’t rely solely on final results.
5. Test trees with only left children, only right children, and those missing one subtree.
6. When analyzing space usage, separately record h, w, and the output length.

Hands-on Compare Four Traversals

1. Manually compute the four tree traversals for a sample tree without running any code.
2. Complete the in-order traversal state table by filling in the state from node 1 to node 6 during iteration.
3. Implement zigzag level-order traversal: traverse even levels left to right, odd levels right to left.
4. Use postorder recursive traversal to compute the subtree size for each node.
5. Construct a chain tree and a perfect tree, both with 31 nodes, and compare the peak stack usage of DFS with the peak queue usage of BFS.

Compare Order and Pending State

Recursion, explicit stacks, and queues all retain pending work. They differ in visiting order and where that state lives. The general DFS auxiliary-space bound depends on tree height h, while BFS scales with the maximum level width w; the resulting list itself consumes an additional O(n). Only when the BST global invariant is satisfied will the in-order traversal produce keys in sorted order.

If input order turns a search tree into a chain, the next chapter on AVL Trees and Rotations explains how to limit its height.

Official References

• Python sys.getrecursionlimit
• Java SE 21 ArrayDeque