Chapter 10a — Tree Problem Patterns
Tree problems always ask the same thing in different costumes: "what does each subtree contribute to the answer?"
Pattern Map
| Problem Signal | Pattern | Direction |
|---|---|---|
| "Height / depth / count of nodes" | Postorder: compute children, combine | Bottom-up |
| "Max/min path sum" | Postorder: return max single-arm, track global | Bottom-up |
| "Validate BST / check property" | Preorder: pass constraints down | Top-down |
| "Right side view / level sums" | BFS level order | Left to right |
| "Kth smallest / inorder sequence" | Inorder on BST | Left to right |
| "LCA" | Postorder: propagate found signal up | Bottom-up |
| "Serialize / deserialize" | Preorder with null markers | Top-down write, queue-based read |
| "Symmetric / mirror" | Simultaneous traversal of left and right | Recursive pairs |
Problem 1: Maximum Depth of Binary Tree
Problem: Find the maximum depth (height) of a binary tree.
maxDepth([3,9,20,null,null,15,7]) → 3
LeetCode 104.
function maxDepth(root) {
if (!root) return 0;
return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}
Dry run:
Tree: 3
/ \
9 20
/ \
15 7
maxDepth(3):
maxDepth(9):
maxDepth(null)=0, maxDepth(null)=0. return 1+max(0,0)=1.
maxDepth(20):
maxDepth(15)=1, maxDepth(7)=1. return 1+max(1,1)=2.
return 1+max(1,2)=3. ✓
Complexity: O(n) time (visits every node), O(h) space (call stack = tree height).
Iterative version (BFS):
function maxDepthBFS(root) {
if (!root) return 0;
const queue = [root];
let depth = 0;
while (queue.length > 0) {
const size = queue.length;
for (let i = 0; i < size; i++) {
const node = queue.shift();
if (node.left) queue.push(node.left);
if (node.right) queue.push(node.right);
}
depth++;
}
return depth;
}
Each level increments depth by 1. Total levels = depth. O(n) time, O(w) space (w = max width).
Problem 2: Invert Binary Tree
Problem: Invert a binary tree (mirror it left to right).
LeetCode 226. Famous for the tweet: "Google: 90% of our engineers use the software you wrote (Homebrew), but you can't invert a binary tree on a whiteboard so f*** off."
function invertTree(root) {
if (!root) return null;
[root.left, root.right] = [root.right, root.left]; // swap children
invertTree(root.left);
invertTree(root.right);
return root;
}
Dry run:
Tree: 4 After inversion: 4
/ \ / \
2 7 7 2
/ \ / \ / \ / \
1 3 6 9 9 6 3 1
invertTree(4):
Swap: left=7, right=2. Tree: 4→[7,2].
invertTree(7):
Swap: left=9, right=6.
invertTree(9): no children. return.
invertTree(6): no children. return.
invertTree(2):
Swap: left=3, right=1.
invertTree(3): no children. return.
invertTree(1): no children. return.
return root(4). ✓
Preorder pattern: Swap first (visit root), then recurse into children. This is correct because swapping at a node doesn't depend on what the children look like internally.
Complexity: O(n) time, O(h) space.
Problem 3: Symmetric Tree
Problem: Check if a binary tree is symmetric (mirror of itself).
isSymmetric([1,2,2,3,4,4,3]) → true
LeetCode 101.
Four Questions
Q1: What do I have? A binary tree.
Q2: What do I want? True if the tree is a mirror of itself around its center.
Q3: What is the brute force? Invert one half, compare with the other. O(n) but destructive.
Q4: Where is the waste? None really — we must check all nodes. The clean solution: simultaneously traverse the tree from both sides, comparing mirror positions.
function isSymmetric(root) {
function isMirror(left, right) {
if (!left && !right) return true; // both null: symmetric
if (!left || !right) return false; // one null, one not: asymmetric
return left.val === right.val &&
isMirror(left.left, right.right) && // outer pair
isMirror(left.right, right.left); // inner pair
}
return isMirror(root.left, root.right);
}
Dry run: isSymmetric([1,2,2,3,4,4,3])
Tree: 1
/ \
2 2
/ \ / \
3 4 4 3
isMirror(2_left, 2_right):
both non-null. 2===2 ✓.
isMirror(3_leftleft, 3_rightright): both val=3. no children. true.
isMirror(4_leftright, 4_rightleft): both val=4. no children. true.
true && true && true = true. ✓
Dry run: isSymmetric([1,2,2,null,3,null,3])
Tree: 1
/ \
2 2
\ \
3 3
isMirror(2_left, 2_right):
2===2 ✓.
isMirror(null, null): true (both null: outer positions).
isMirror(3_left, 3_right): 3===3.
isMirror(null, null): true.
isMirror(null, null): true.
true.
true && true && true = true.
Wait — the tree [1,2,2,null,3,null,3] is:
left 2 has no left child, right child=3.
right 2 has no left child, right child=3.
isMirror(2L, 2R):
2===2 ✓.
outer: isMirror(2L.left, 2R.right) = isMirror(null, node(3)) → false!
false. ✓ (this tree is NOT symmetric — [1,2,2,null,3,null,3])
Complexity: O(n) time, O(h) space.
Problem 4: Diameter of Binary Tree
Problem: Find the length of the longest path between any two nodes (number of edges).
diameterOfBinaryTree([1,2,3,4,5]) → 3 (path: 4→2→1→3 or 4→2→5)
LeetCode 543.
Built in Chapter 10, Part 7. Full implementation:
function diameterOfBinaryTree(root) {
let maxDiam = 0;
function height(node) {
if (!node) return -1;
const lh = height(node.left);
const rh = height(node.right);
// Diameter through this node: left arm + right arm
// (lh+1) edges from this node down left + (rh+1) edges down right
maxDiam = Math.max(maxDiam, lh + rh + 2);
return 1 + Math.max(lh, rh);
}
height(root);
return maxDiam;
}
Full dry run: Tree [1,2,3,4,5]
1
/ \
2 3
/ \
4 5
height(4): lh=-1, rh=-1. diameter=(-1)+(-1)+2=0. maxDiam=0. return 0.
height(5): lh=-1, rh=-1. diameter=0. maxDiam=0. return 0.
height(2): lh=0, rh=0. diameter=0+0+2=2. maxDiam=2. return 1.
height(3): lh=-1, rh=-1. diameter=0. maxDiam=2. return 0.
height(1): lh=1, rh=0. diameter=1+0+2=3. maxDiam=3. return 2.
return 3. ✓
Why lh + rh + 2 and not lh + rh? lh is the height of the left subtree (number of edges from this node's left child to the deepest leaf). The arm from this node going left has lh + 1 edges (one to reach the left child, then lh more). Same for right: rh + 1. Total diameter = (lh+1) + (rh+1) = lh + rh + 2.
Alternative: If height is defined as number of nodes (not edges), adjust accordingly. The problem asks for number of edges.
Problem 5: Binary Tree Maximum Path Sum
Problem: Find the maximum path sum. A path can start and end at any node.
maxPathSum([-10,9,20,null,null,15,7]) → 42 (path: 15→20→7)
LeetCode 124. Hard. Most asked hard tree problem.
Four Questions
Q1: What do I have? A binary tree where nodes can have negative values.
Q2: What do I want? Maximum sum of any path (path = connected sequence of nodes, no repeated nodes).
Q3: What is the brute force? For every pair of nodes, find the path between them and sum it. O(n²).
Q4: Where is the waste? Recomputing subtree contributions. Every path has a highest node (the "apex"). At each node as apex: gain = max_left_gain + node.val + max_right_gain. But when this node contributes to its parent's path, it can only extend in one direction (left or right, not both — that would branch). Return node.val + max(left_gain, right_gain, 0) to parent.
function maxPathSum(root) {
let globalMax = -Infinity;
function maxGain(node) {
if (!node) return 0;
// Max gain from left/right subtrees (ignore negative paths with max(0, ...))
const leftGain = Math.max(0, maxGain(node.left));
const rightGain = Math.max(0, maxGain(node.right));
// Price of path through current node as apex
const priceThroughNode = node.val + leftGain + rightGain;
globalMax = Math.max(globalMax, priceThroughNode);
// Return max gain if continuing path through parent (can only go one direction)
return node.val + Math.max(leftGain, rightGain);
}
maxGain(root);
return globalMax;
}
Dry run: maxPathSum([-10,9,20,null,null,15,7])
Tree: -10
/ \
9 20
/ \
15 7
maxGain(9): left=max(0,0)=0, right=max(0,0)=0. price=9+0+0=9. max=9. return 9.
maxGain(15): left=0, right=0. price=15. max=15. return 15.
maxGain(7): left=0, right=0. price=7. max=15. return 7.
maxGain(20):
leftGain=max(0,15)=15. rightGain=max(0,7)=7.
price=20+15+7=42. globalMax=42.
return 20+max(15,7)=35.
maxGain(-10):
leftGain=max(0,9)=9. rightGain=max(0,35)=35.
price=-10+9+35=34. globalMax stays 42.
return -10+max(9,35)=25.
return 42. ✓ (path: 15→20→7)
Why max(0, childGain)? If a subtree has negative total gain, we don't include it — we take 0 instead (don't extend the path into that subtree). A path can start anywhere, so choosing not to go left is valid.
Complexity: O(n) time, O(h) space.
Problem 6: Lowest Common Ancestor of a BST
Problem: Find LCA of two nodes in a BST (not generic binary tree).
lowestCommonAncestor(root, p=2, q=8) → 6 (for BST with root 6)
LeetCode 235.
In a BST, we can use the BST property to avoid checking both subtrees:
- If both p and q are less than root → LCA is in left subtree.
- If both p and q are greater than root → LCA is in right subtree.
- If they're on different sides (or one equals root) → root is the LCA.
function lowestCommonAncestorBST(root, p, q) {
while (root) {
if (p.val < root.val && q.val < root.val) {
root = root.left; // both in left subtree
} else if (p.val > root.val && q.val > root.val) {
root = root.right; // both in right subtree
} else {
return root; // split point or one equals root
}
}
return null;
}
Dry run: LCA of 2 and 8 in BST [6,2,8,0,4,7,9,null,null,3,5]
root=6. p=2<6, q=8>6 → split point. return node(6). ✓
Dry run: LCA of 2 and 4 in same BST
root=6. p=2<6, q=4<6 → both left. root=node(2).
root=2. p=2=2, split (p equals root). return node(2). ✓
Complexity: O(h) time — we only follow one path. O(1) space (iterative). This is O(log n) for balanced BST vs O(n) for the generic LCA that must check both subtrees.
Problem 7: Construct Binary Tree from Preorder and Inorder
Problem: Given preorder and inorder traversal arrays, reconstruct the binary tree.
buildTree([3,9,20,15,7], [9,3,15,20,7]) → the tree with root 3
LeetCode 105.
Four Questions
Q1: What do I have? Preorder array and inorder array of the same tree.
Q2: What do I want? Reconstruct the original tree.
Q3: What is the brute force? The first preorder element is always the root. Find it in inorder — everything left of it is the left subtree, everything right is the right subtree. Recurse. O(n²) if searching inorder array linearly.
Q4: Where is the waste? Repeated linear search in inorder. Use a HashMap: inorder value → index. O(n) total.
function buildTree(preorder, inorder) {
const inMap = new Map();
inorder.forEach((val, idx) => inMap.set(val, idx));
let preIdx = 0;
function build(left, right) {
if (left > right) return null;
const rootVal = preorder[preIdx++]; // next preorder val = current root
const root = new TreeNode(rootVal);
const inIdx = inMap.get(rootVal); // position in inorder
root.left = build(left, inIdx - 1); // left subtree: inorder left of root
root.right = build(inIdx + 1, right); // right subtree: inorder right of root
return root;
}
return build(0, inorder.length - 1);
}
Dry run: buildTree([3,9,20,15,7], [9,3,15,20,7])
inMap: {9:0, 3:1, 15:2, 20:3, 7:4}. preIdx=0.
build(0, 4):
rootVal=preorder[0]=3. preIdx=1. inIdx=inMap[3]=1.
root.left = build(0, 0): ← left subtree: inorder[0..0]=[9]
rootVal=preorder[1]=9. preIdx=2. inIdx=inMap[9]=0.
root.left = build(0,-1)=null.
root.right = build(1,0): left(1)>right(0) → null.
return node(9).
root.right = build(2, 4): ← right subtree: inorder[2..4]=[15,20,7]
rootVal=preorder[2]=20. preIdx=3. inIdx=inMap[20]=3.
root.left = build(2, 2):
rootVal=preorder[3]=15. preIdx=4. inIdx=inMap[15]=2.
left=null, right=null. return node(15).
root.right = build(4, 4):
rootVal=preorder[4]=7. preIdx=5. inIdx=4.
left=null, right=null. return node(7).
return node(20) with children 15 and 7.
return node(3) with left=9 and right=20. ✓
Why preorder gives the root and inorder gives the split? Preorder visits root first → first element is always the current subtree's root. Inorder visits left subtree completely before root → root's position in inorder divides left and right subtrees.
Complexity: O(n) time (HashMap makes each lookup O(1)), O(n) space.
Problem 8: Serialize and Deserialize Binary Tree
Problem: Design encode/decode for a binary tree. LeetCode 297. Hard.
Why Inorder Alone Doesn't Work
Inorder [1,2,3] could represent:
2 1 3
/ \ \ /
1 3 2 2
\ /
3 1
Multiple trees share the same inorder. Inorder is ambiguous for reconstruction.
Preorder + Null Markers = Unambiguous
Preorder with explicit null markers uniquely encodes any binary tree:
1
/ \
2 3
/
4
Preorder + nulls: "1,2,4,null,null,null,3,null,null"
function serialize(root) {
const result = [];
function preorder(node) {
if (!node) { result.push('null'); return; }
result.push(String(node.val));
preorder(node.left);
preorder(node.right);
}
preorder(root);
return result.join(',');
}
function deserialize(data) {
const nodes = data.split(',');
let idx = 0;
function build() {
if (nodes[idx] === 'null') { idx++; return null; }
const node = new TreeNode(Number(nodes[idx++]));
node.left = build();
node.right = build();
return node;
}
return build();
}
Dry run: Serialize [1,2,null,null,3,4,null,null,5,null,null]
Tree: 1
/ \
2 3
/ \
4 5
Serialize preorder+null:
visit 1 → "1"
visit 2 → "2"
visit null (2.left) → "null"
visit null (2.right) → "null"
visit 3 → "3"
visit 4 → "4"
visit null (4.left) → "null"
visit null (4.right) → "null"
visit 5 → "5"
visit null (5.left) → "null"
visit null (5.right) → "null"
Result: "1,2,null,null,3,4,null,null,5,null,null"
Dry run: Deserialize
nodes=["1","2","null","null","3","4","null","null","5","null","null"]. idx=0.
build(): val="1", node=1. idx=1.
build(): val="2", node=2. idx=2.
build(): val="null". idx=3. return null.
build(): val="null". idx=4. return null.
2.left=null, 2.right=null. return node(2).
build(): val="3", node=3. idx=5.
build(): val="4", node=4. idx=6.
build(): "null". return null. idx=7.
build(): "null". return null. idx=8.
return node(4).
build(): val="5", node=5. idx=9.
build(): "null". null. idx=10.
build(): "null". null. idx=11.
return node(5).
3.left=node(4), 3.right=node(5). return node(3).
1.left=node(2), 1.right=node(3). return node(1). ✓
Why preorder works for reconstruction: When deserializing, the first value is always the current subtree's root. Null markers tell us exactly where left and right subtrees end — they encode structure, not just values.
Complexity: O(n) time and space for both.
Pattern Recognition Decision Tree
New tree problem:
1. Need a value computed FROM the subtrees (height, sum, count)?
→ Postorder. Return value from children, combine at current node.
→ If tracking a global optimum: update a global variable in postorder.
2. Need to PASS information DOWN the tree (bounds, target, prefix)?
→ Preorder. Pass state as function arguments.
3. BST + sorted order + kth element?
→ Inorder traversal. Count elements as you visit.
4. Level-by-level (width, level sums, minimum depth)?
→ BFS with queue. Process levelSize nodes per iteration.
5. Find LCA?
→ Generic tree: postorder, return node when found, combine at split.
→ BST: use BST property, O(log n) iterative.
6. Validate BST?
→ Preorder with min/max bounds passed as arguments.
7. Serialize/reconstruct?
→ Preorder with null markers. Deserialize using index/queue.
8. Mirror/symmetric?
→ Simultaneous recursive comparison of mirror positions.
5 Practice Problems
1. Trace and Predict
function f(root) {
if (!root) return [];
const result = [];
const queue = [root];
while (queue.length) {
const level = [], size = queue.length;
for (let i = 0; i < size; i++) {
const node = queue.shift();
if (i === size - 1) result.push(node.val); // last node in level
if (node.left) queue.push(node.left);
if (node.right) queue.push(node.right);
}
}
return result;
}
What does this function return? Trace on [1,2,3,null,5,null,4]. Name this problem (LeetCode 199).
2. Find the Waste
Computing the diameter naively:
For each node n, compute height(n.left) + height(n.right) + 2.
If height is a separate function called for every node, this is O(n²).
Measure the waste precisely: for a perfect binary tree of height h (2^(h+1)-1 nodes), how many height computations does the naive approach make in total? Show it is O(n²). Then explain how the combined postorder approach (Part 7) reduces this to O(n).
3. Failure Analysis
function isBalanced(root) {
if (!root) return true;
const lh = height(root.left);
const rh = height(root.right);
return Math.abs(lh - rh) <= 1 &&
isBalanced(root.left) &&
isBalanced(root.right);
}
This is O(n²) because height is called repeatedly. Write the O(n) version using the pattern from the diameter problem (returning -1 as a sentinel for "unbalanced"). Trace both on a skewed tree [1,2,null,3,null,null,null] and verify the O(n) version returns early.
4. Design Under Constraints
Design pathSum(root, targetSum) (LeetCode 113 — Path Sum II): find all root-to-leaf paths that sum to targetSum.
Constraint: must return the actual paths (lists of node values), not just a count.
Tree: 5
/ \
4 8
/ / \
11 13 4
/ \ \
7 2 1
targetSum=22.
Paths: [5,4,11,2] and [5,8,4,1].
Design the preorder DFS with backtracking. When do you add to the result? When do you backtrack? Why must you push to currentPath before recursing and pop after?
5. Reach Beyond
Design countNodes(root) (LeetCode 222): count nodes in a complete binary tree in O(log²n) time (not O(n)).
A complete binary tree: all levels full except possibly the last, which is filled left to right. Every complete binary tree has either a perfect left subtree or a perfect right subtree (or both).
Key insight: compute leftHeight (go left until null) and rightHeight (go right until null).
- If
leftHeight === rightHeight: left subtree is perfect →2^leftHeight - 1 + 1 (root) + countNodes(root.right). - If
leftHeight > rightHeight: right subtree is perfect with one less level →countNodes(root.left) + 2^rightHeight - 1 + 1 (root).
Each recursive call reduces the problem by half. Time complexity: O(log²n). Why is this better than O(n)? When would you use this in production (hint: heap data structure stored as a tree)?