Lab 09 — Tree Traversal Fundamentals

Goal

Master the three depth-first traversals (preorder, inorder, postorder) in both recursive and iterative forms, plus level-order (BFS). Understand the explicit-stack simulation of recursion, the postorder trick, and Morris traversal as the O(1)-space follow-up. The deliverable: implement iterative inorder cleanly and explain the stack invariant.

Background Concepts

Binary trees; DFS vs BFS; recursion as implicit stack; explicit stack as iterative replacement; visited flags. Review the Trees section and the Stacks section of the Phase 1 README.

Interview Context

Tree traversal is a Day-1 interview topic. Recursive forms are trivial; the interesting signal is iterative inorder (the canonical “implement recursion with a stack” question). Postorder iteratively is harder still — and Morris traversal (O(1) space) shows up in senior interviews.

Problem Statement

Given the root of a binary tree, return the inorder traversal as a list. Implement iteratively (no recursion).

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

Constraints

  • Number of nodes in [0, 10^4].
  • -100 ≤ Node.val ≤ 100.
  • The tree is not necessarily balanced.

Clarifying Questions

  1. What’s the node definition? (As above — confirm with interviewer.)
  2. Empty tree allowed? (Yes — return [].)
  3. Duplicate values? (Allowed; doesn’t affect traversal.)
  4. Are we limited on stack space? (For 10^4 nodes in a degenerate (linked-list) tree, recursive blows Python’s default 1000-deep stack. Iterative is required.)
  5. Must we use O(1) extra space? (If yes — Morris traversal. Otherwise the explicit stack is fine.)

Examples

TreeInorder
[1, null, 2, 3] (LeetCode array form)[1, 3, 2]
[][]
[1][1]
BST [2, 1, 3][1, 2, 3] (sorted!)

Initial Brute Force

Recursive — visit left, root, right.

def inorder_recursive(root):
    out = []
    def rec(node):
        if not node: return
        rec(node.left)
        out.append(node.val)
        rec(node.right)
    rec(root)
    return out

Brute Force Complexity

O(N) time, O(H) space (recursion stack, where H = tree height). H = N for a degenerate tree, log N for balanced.

Optimization Path

The iteration cost is the same — O(N) — but recursion uses the system stack which has a fixed limit (~1000 frames in Python by default). For N = 10⁴ in a worst-case skewed tree, recursion crashes. We replace with an explicit stack.

The pattern: “go left as far as possible, pushing each node along the way; when we can’t go further left, pop, visit, then move to right child and repeat.”

Final Expected Approach

def inorder_iterative(root):
    out, stack, node = [], [], root
    while node or stack:
        while node:                  # walk left, pushing
            stack.append(node)
            node = node.left
        node = stack.pop()           # leftmost unvisited
        out.append(node.val)         # visit
        node = node.right            # explore right subtree
    return out

For preorder: visit before descending left.

def preorder_iterative(root):
    if not root: return []
    out, stack = [], [root]
    while stack:
        node = stack.pop()
        out.append(node.val)
        if node.right: stack.append(node.right)  # right first → left popped first
        if node.left:  stack.append(node.left)
    return out

For postorder: hardest. Two clean approaches:

  1. Modified preorder + reverse: do preorder but visit right before left; reverse the result.
  2. Visited-flag trick: push (node, visited) tuples; on first pop, push back as visited and push children; on second pop, emit.
def postorder_iterative(root):
    if not root: return []
    out, stack = [], [root]
    while stack:
        node = stack.pop()
        out.append(node.val)
        if node.left:  stack.append(node.left)
        if node.right: stack.append(node.right)
    return out[::-1]

Data Structures Used

  • An explicit stack (list/deque/Stack/std::stack).
  • A pointer/cursor node.
  • An output list.
  • For Morris: only the output list and tree pointers themselves.

Correctness Argument

Inorder invariant: at the start of each outer-loop iteration, the stack contains the chain of ancestors (along left-edges) of the next-to-visit node, all of whose left subtrees are pending. The inner while node walk pushes new ancestors. After popping, we’ve finished its left subtree (it was either null or fully consumed in earlier iterations); we visit it; then move to its right subtree, where the same invariant resumes.

Termination: every node is pushed exactly once and popped exactly once (visited once). N pushes + N pops = O(N) work. Loop ends when both node is null and stack is empty — meaning we’ve returned from the rightmost-rightmost subtree.

Complexity

O(N) time, O(H) auxiliary space (the stack holds at most one chain of ancestors).

For a skewed tree, H = N. For balanced, H = log N.

Implementation Requirements

  • Initialize node = root, stack = [].
  • Outer loop: while node or stack.
  • Inner loop walks left and pushes.
  • After inner loop: pop, append val, set node = popped.right.
  • Don’t push None. Don’t visit on the way down.
  • For preorder, push right before left (LIFO order).
  • For postorder, the “modified preorder + reverse” form is the cleanest one-pass solution.

Tests

  • Smoke: the example table.
  • Unit: single node; empty tree; left-skewed (degenerate); right-skewed; balanced BST.
  • Property: inorder of a BST is sorted ascending.
  • Property: preorder + inorder uniquely determine a binary tree (round-trip test if you implement the reconstruction).
  • Edge: root with only-left child; root with only-right child.
  • Large: N = 10⁴ skewed tree — must not stack-overflow.

Follow-up Questions

  • “Implement Morris traversal (O(1) space).” → temporarily rewire the tree using “threaded” pointers from inorder predecessors back to successors; restore on the way through.
  • “Level-order traversal.” → BFS with a queue.
  • “Zigzag level-order.” → BFS with alternating direction; reverse every other level.
  • “Reconstruct a tree from its preorder + inorder.”
  • “Boundary traversal of a tree.” → combination of left boundary, leaves left-to-right, right boundary reversed.
  • “Verify a BST.” → inorder traversal must be strictly ascending; or carry (min, max) bounds recursively.

Product Extension

A directory tree being indexed: BFS gives breadth-first crawl (sibling priority); preorder DFS visits parent before children (renderers); postorder visits children before parent (size accumulation, deletion). A code formatter walks the AST in postorder so children’s formatted text is available when the parent emits its own. A serializer uses preorder. The choice of traversal is a design decision tied to dependency direction.

Language/Runtime Follow-ups

  • Python: list works as stack via append/pop. collections.deque is faster for very deep stacks. Default recursion limit is 1000 — sys.setrecursionlimit(10**5) if recursing on huge trees.
  • Java: Deque<TreeNode> stack = new ArrayDeque<>(). Avoid java.util.Stack (legacy, synchronized). For BFS, use Deque<TreeNode> q = new ArrayDeque<>().
  • Go: slices as stacks: stack = append(stack, n), pop with stack = stack[:len(stack)-1]. No generic stack in stdlib pre-1.18.
  • C++: std::stack<TreeNode*> and std::queue<TreeNode*>.
  • JS/TS: array push/pop. For BFS, Array.shift() is O(N); use a real deque or an index pointer to avoid quadratic blowup on large trees.
  • Recursion depth: Python ~1000 default; Java ~10⁴ on default -Xss; Go grows stacks dynamically. For 10⁴ skewed trees, iterative is mandatory in Python.

Common Bugs

  1. Pushing None onto the stack — bloats the stack and requires defensive pops.
  2. Visiting on the way down for inorder — that’s preorder.
  3. In preorder iterative, pushing left before right — gives reverse-of-preorder.
  4. For postorder, forgetting to reverse in the modified-preorder approach.
  5. BFS using list.pop(0) in Python — O(N) shift on every level; quadratic on deep trees. Use collections.deque and popleft().
  6. Inner loop not consuming left children — only pushing root; you never reach the leftmost node.
  7. Mutation in Morris traversal — forgetting to restore the threaded pointer; leaves the tree corrupted.

Debugging Strategy

  • Print stack contents and node at the top of each outer-loop iteration.
  • For inorder, the first visit should be the leftmost node.
  • For a known BST, the output of inorder must be sorted; if not, the loop is wrong.
  • For large skewed inputs, iterative must finish without RecursionError.

Mastery Criteria

  • Wrote iterative inorder from memory in under 3 minutes.
  • Stated the stack invariant (chain of ancestors along left edges).
  • Wrote preorder iteratively and explained the right-before-left push order.
  • Articulated two postorder strategies (reverse-preorder vs visited-flag).
  • Knew that BFS uses a queue; can explain why list.pop(0) is wrong in Python.
  • Could sketch Morris traversal at a high level: rewire to predecessors, restore on the way through.
  • Recognized that inorder of a BST is sorted (and used it to verify a BST).