Trees, Recursion, And Binary Search Trees

What's being tested

These problems test recursive tree traversal, careful base-case design, and choosing the right aggregation for each node’s subtree. You must distinguish general binary-tree logic from BST ordering, then state correctness, complexity, and edge-case behavior clearly.

Patterns & templates

• Depth-first recursion — return subtree height or best contribution; define null explicitly, typically O(n) time and O(h) call-stack space.

• N-ary tree height — compute 1 + max(child heights); initialize the maximum correctly and clarify whether depth counts nodes or edges.

• Postorder dynamic programming — combine left result, node value, and right result after recursive calls; useful for height balance and maximum path sum.

• BST LCA — compare both targets with the current value; move left when both are smaller, right when both are larger, otherwise current node is the split point.

• Catalan recurrence — distinct BST shapes satisfy $C_n=\sum_{i=1}^{n} C_{i-1}C_{n-i}$; use bottom-up DP and 64-bit integers for n ≤ 19.

• Maximum path sum — return the best downward gain while separately tracking a path that bends through the node; clamp negative child gains to zero.

• Level-order encoding — map array indices consistently, validate missing children, and avoid assuming every position represents an existing node in sparse representations.

Common pitfalls

Pitfall: Confusing node depth with edge depth, or returning only root-to-leaf paths when the maximum path may start and end anywhere.

Pitfall: Claiming O(log n) for BST operations without stating the tree is balanced; an unbalanced BST can degrade to O(n).

Pitfall: Forgetting null, single-node, duplicate-key, negative-value, and “target not present” behavior when explaining correctness.

Practice these

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