CONCEPT · 75 minutes
DFS traversal orders, BST invariants, level-order BFS, and the recursive thinking that makes most tree problems feel like the same problem at a different scale.
When I first saw a recursive tree traversal, it felt like magic. Three lines of code, and you visit every node in a tree of arbitrary size and shape. What took me longer to understand was why it works — and once I understood that, tree problems stopped feeling unpredictable and started feeling like templates.
Trees are self-similar. Every subtree is also a tree. That one fact makes many tree algorithms elegant: to process a tree, process the root, then recursively process each subtree. The algorithm handles one node at a time; the recursion handles all the rest. The base case is a null node — return immediately.
Analogy: Think of a company org chart. The CEO has direct reports; each of them has their own direct reports; and so on down to individual contributors who report to no one. To find everyone in a department, you start at the department head, visit them, then recursively do the same for each of their reports. The "leaf nodes" are the people with no reports — you stop there. That is exactly what recursive tree traversal does: one rule, applied uniformly at every level.
This pattern comes up directly in workflow-engine-rs. The workflow graph is a DAG, and walking it to compute execution order is the same depth-first post-order logic you see in tree traversals: a node's dependencies must be resolved before the node itself can run. The same mental model, just without the "exactly two children" constraint.
Space complexity — the hidden cost of elegant recursion: every recursive call adds a frame to the call stack. A balanced tree uses O(log n) frames; a degenerate path-shaped tree uses O(n). On very deep trees, this is where the elegant recursive code hits a RecursionError — and it's why the iterative version exists. Always state space as O(h), then note what h is for the expected tree shape.
DFS on a binary tree visits nodes in a fixed order relative to left subtree, root, and right subtree:
graph TD
subgraph "Tree"
A["4"] --> B["2"]
A --> C["6"]
B --> D["1"]
B --> E["3"]
C --> F["5"]
C --> G["7"]
end
subgraph "Traversal orders"
P["Pre-order: 4, 2, 1, 3, 6, 5, 7"]
I["In-order: 1, 2, 3, 4, 5, 6, 7 (sorted on BST)"]
Po["Post-order: 1, 3, 2, 5, 7, 6, 4"]
endWhen to use each order:
The height of a tree equals one more than the maximum height of its subtrees. You need the children's heights before computing the root's — post-order.
A Binary Search Tree has a strict invariant: for every node, all values in the left subtree are strictly less than the node's value, and all values in the right subtree are strictly greater. Not just immediate children — every descendant.
This invariant makes search O(h).
Analogy: A BST is a sorted dictionary that discards half its remaining pages with each lookup. You open to the middle: if your word comes before the current entry, tear out the right half and repeat; if after, tear out the left half. At every node, the BST invariant tells you which half is safe to discard. That directed elimination is what gives O(h) search instead of O(n) linear scan.
The naive approach checks left.val < node.val < right.val at each node. This misses violations spanning multiple levels:
The classic BST validation bug: root=5, right child=6, right child's left child=3. Local checks all pass (3 < 6, 2 < 5 < 6), but 3 is in the right subtree of 5 where only values > 5 belong. The correct validator propagates min/max bounds down the recursion — every node's value must stay within the bounds set by its ancestors.
BFS visits nodes level by level. Use it when the problem cares about depth: minimum depth, right side view, zigzag traversal. (Always use collections.deque, not list.pop(0).)
The level-size snapshot: level_size = len(queue) captures how many nodes are at the current level before any children are added. The inner for _ in range(level_size) processes exactly that many nodes. This is the standard BFS level-capture pattern — memorize it.
Try these from memory:
[4, 2, 6, 1, 3, 5, 7] (root=4), write out the in-order traversal. What does in-order give you on any valid BST?left.val < node.val < right.val at each node) fail? What does the correct version propagate?level_size = len(queue) before the inner loop, not inside it?Reflective prompt: the three DFS traversals (pre, in, post) are structurally identical — they differ only in where result.append(node.val) appears. Before the recursive calls (pre-order), between them (in-order), or after both (post-order). The choice is driven by when you need the current node's result relative to its children's results. What other algorithms in this path have a similar "same structure, different placement" property? How does noticing that pattern change how you memorize algorithms?
Problem: Lowest Common Ancestor of a BST
Given a BST and two nodes p and q guaranteed to exist in the tree, find their Lowest Common Ancestor (LCA) — the lowest node that has both as descendants (a node is a descendant of itself).
LCA(2, 8) = 6 | LCA(2, 4) = 2 | LCA(0, 5) = 2
The BST shortcut: if both targets are less than the current node, LCA is in the left subtree. If both are greater, it's in the right. Otherwise, the current node is the LCA.
Hint 1: The three cases are: both p and q are less than node.val (go left), both are greater (go right), or they split (current node is LCA). The "else" covers p.val == node.val, q.val == node.val, and the split case.
Hint 2: The iterative version uses O(1) extra space. The equivalent recursive version is one line shorter but uses O(h) call stack. Prefer iterative when space matters.
Hint 3: You are guaranteed that p and q are in the tree, so the while loop will always find the LCA before node becomes None.
Why the BST LCA is elegant: without the BST constraint, finding the LCA requires DFS from the root, ancestor tracking, or the two-pass algorithm — O(n). With the BST constraint, you walk directly to the LCA in O(h) using just the invariant. This is the BST invariant earning its keep on a problem that is not a search problem — it gives you directional information even when you are not looking for a specific value.
Application-level questions on tree traversal, BST invariants, and BFS
1. You run in-order DFS on a valid BST. What is the order of values in the output?
Correct Answer: C
In-order DFS visits left subtree, then root, then right subtree. On a BST where every left child is smaller and every right child is larger, this visits nodes in ascending order. This is why 'inorder traversal of BST gives sorted output' is a standard fact.
2. A naive BST validator checks `node.left.val < node.val < node.right.val` at every node. What bug does this miss?
Correct Answer: B
The BST invariant requires ALL values in the left subtree to be less than the root (and all in the right to be greater). A tree like [5, 4, 6, null, null, 3, 7] would pass the local check at 5 (4<5<6) but violates the global invariant (3 is in the right subtree of 5 but 3<5). The correct validator passes min/max bounds down the recursion.
3. Recursive DFS on a tree of height h uses how much call-stack space?
Correct Answer: B
Recursive DFS adds one stack frame per level. The maximum depth of the recursion equals the tree height h. For a balanced tree h = O(log n); for a path-like tree (a linked list) h = O(n). Always state the space complexity in terms of h, not n.
4. Which traversal order is most natural for serializing a tree so you can reconstruct it later?
Correct Answer: C
Pre-order (root, left, right) serializes a tree so that during deserialization, when you process a value, you know it's the root of the current subtree — the left subtree values follow immediately, then the right. This makes recursive reconstruction natural. Level-order also works but requires handling null markers differently.
5. BFS uses a queue; DFS uses a stack (or recursion). Which traversal should you choose to find the shortest path from root to a node in a tree?
Correct Answer: B
BFS explores nodes level by level. The first time it reaches the target node, that path is guaranteed to be the shortest (fewest edges from root). DFS might find a path, but not necessarily the shortest one. 'Minimum depth of binary tree' is a canonical BFS problem.