Trees, Recursion, And BST Traversal

What's being tested

These problems test recursive tree traversal, BST-ordered navigation, and careful handling of hierarchical data with depth, keys, or ancestry constraints. Interviewers are probing whether you can choose the right traversal shape, preserve invariants, and explain complexity without overcomplicating the implementation.

Patterns & templates

• Postorder recursion for aggregation — compute child results before parent; useful for depth, weighted sums, and merge semantics; O(n) time.

• DFS with return values — functions like lca(root, p, q) return “found node/subtree answer”; avoid global state unless it simplifies proof.

• BST predecessor/successor traversal — split around target, then advance two iterators; O(h + k) time, O(h) space.

• Keyed child reconciliation — merge N-ary children using Map<key, node>; preserve deterministic ordering if the prompt requires it.

• Two-pass depth computation — first compute maxDepth, then sum using weight maxDepth - depth + 1; alternative BFS level-sum avoids explicit weights.

• Null/base-case discipline — define behavior for empty tree, missing nodes, duplicate keys, leaf depth, and single-node trees before coding.

• Complexity narration — use n for total nodes, h for tree height, k for requested outputs; distinguish balanced vs skewed BSTs.

Common pitfalls

Pitfall: Treating an N-ary tree like a binary tree; always clarify child representation and key uniqueness before merging.

Pitfall: For LCA, returning a node when only one target exists unless the prompt guarantees both nodes are present.

Pitfall: For k closest in BST, doing full inorder sort when the expected solution uses ordered traversal and stops after k.

Practice these

The practice cards below cover the canonical variants — solve all of them and time yourself.