Preview — Pro guide
You are seeing a portion of this guide. Sign in and upgrade to unlock the full article, quizzes, and interview answers.
Binary Trees & BST: Traversals, LCA, and Classic Patterns
Master binary tree traversals (DFS, BFS, iterative), BST operations with full complexity analysis, Lowest Common Ancestor, and serialize/deserialize. Covers the recursive template that solves 80% of tree interview problems.
Why Tree Problems Are Different — The Single-Node Mental Model
Tree problems feel hard because candidates try to reason about the whole tree at once. The correct mental model: think about what a single node needs to compute and what it must return to its parent. If you can answer that for one node, recursion handles the rest.
Every recursive tree function has the same skeleton: (1) base case — what to return for None; (2) recurse left and right; (3) combine left/right results to produce the current node's return value. The entire art of tree problems is step 3.
For height: current node returns 1 + max(left_height, right_height). For diameter (LC 543): the longest path through the current node is left_height + right_height, but you return the height (1 + max(...)) to the parent. The diameter is tracked as a side effect via a nonlocal variable. This pattern — return one thing, track another as a side effect — appears in at least 10 common tree problems.
For tree problems that ask for a path sum (LC 112, 113, 124): distinguish between path-through-root (passes through current node) and any-path (can start and end anywhere). Any-path problems require the side-effect pattern.
The other key insight: inorder traversal of a BST yields a sorted array. This equivalence converts many BST problems into sorted-array problems. Kth smallest in BST? Inorder traversal, return kth element. Validate BST? Inorder traversal must be strictly increasing.
How to Approach Any Tree Problem in an Interview
Confirm tree type and constraints
Ask: is this a BST (values matter) or a general binary tree (structure only)? Are values unique? Can the tree be empty? Can it be unbalanced? For BST problems this changes your algorithm entirely.
Identify the question category
Tree problems fall into: traversal (what order?), construction (build from arrays), path (sum/length between nodes), BST operations (insert/delete/validate), or LCA/ancestors. Each category has a go-to technique.
Write the base case first
Every recursive tree function must handle if not node: return <base> as the first line. For height, base is 0. For path sum, base is target == 0 at leaf. Getting this wrong causes null pointer crashes.
Apply the single-node mental model
Ask: what does this node need to return to its parent? Think at the level of a single node, not the whole tree. If you need to track a global result AND return something to the parent, use the 'return one thing, side-effect another' pattern.
Choose traversal order from the dependency
Preorder (root first) when parent values are needed before children. Postorder (root last) when children must be computed before the parent — height, diameter, path sum all require postorder. BFS for level-based problems.