Module 7

Trees & traversals

A tree is nesting made visible — file systems, org charts, JSON, the DOM, expression syntax — and a binary tree (≤ 2 children) is its interview form. The special case that earns its keep is the binary search tree: everything in a node's left subtree is smaller, everything right is larger, recursively. That invariant turns search, insert and delete into binary-search-shaped walks: O(log n) — if the tree stays balanced. Insert sorted data naively and the BST degenerates into a linked list, O(n); that single caveat (and the existence of self-balancing trees that prevent it) is the most common tree follow-up question there is.

Traversalsare the alphabet. The three depth-first orders are one recursive function with the “emit the root” line moved: before the children (pre-order — serialize/copy), between them (in-order — sorted output from a BST), after them (post-order — children before parents: deletion, evaluating expression trees, computing subtree sizes). Level-orderdrops recursion for a queue and visits by depth — it's just BFS.

🎛 Four traversals, one tree

visit order: 20 → 30 → 40 → 50 → 60 → 70 → 80← sorted! (it's a BST)

In-order (L, root, R) — classic use: BST → sorted output. The three depth-first orders differ only in when the root is emitted; BFS swaps the implicit stack for an explicit queue.

The template that solves most tree problems

def solve(node):
    if node is None:            # base case: the empty tree
        return EMPTY_ANSWER
    left  = solve(node.left)    # trust the recursion
    right = solve(node.right)
    return combine(left, right, node.val)

# height:   EMPTY=0,      combine = 1 + max(left, right)
# size:     EMPTY=0,      combine = 1 + left + right
# max path: EMPTY=0,      combine = node.val + max(left, right, 0)
# valid BST: pass down (lo, hi) bounds instead — check lo < val < hi

Height, size, depth, balance checks, mirror checks, path sums — all the same three lines with a different combine. Cost: O(n) time (each node once), O(height) stack space — O(log n) balanced, O(n) degenerate. Quote both.

Choosing a traversal in one line each

Pre-order — need the parent's decision before visiting children (copying, serializing, prefix notation).
In-order — need BST contents in sorted order (validation, k-th smallest).
Post-order — need children's answers to compute the parent's (sizes, heights, safe deletion).
Level-order/BFS — need results grouped by depth, or the nearest anything.

Say it out loud

“In-order on a BST yields sorted order — so validating the BST is checking that sequence ascends.”
“O(log n) assumes balance; worst case this is a list. Self-balancing variants — red-black, AVL — keep the guarantee.”
“Space here is the recursion stack: O(height), not O(1).”

← Searching & sorting Next: Graphs →