Blind 75 — Tree Pattern Guide

How to Identify a “Tree” Problem

Interview Triggers

• Input is TreeNode root
• Mention of binary tree, BST, left/right children, parent
• “Depth”, “height”, “diameter”, “path sum”
• “Level order”, “zigzag”, “right view”
• “Lowest common ancestor”
• “Serialize / deserialize”
• “Construct tree from traversals”

Which Sub-Pattern Does It Belong To?

If the prompt says…	Use this sub-pattern	Example LC
Find max depth / height	DFS post-order	104
Compare two trees node-by-node	DFS simultaneous	100
Mirror the tree	DFS swap children	226
Max path sum (any node-to-node)	DFS with global tracker	124
Level-by-level traversal	BFS with size loop	102
Serialize / deserialize	Preorder + sentinel (“null”)	297
Is T a subtree of S?	DFS + sameTree on each node	572
Build tree from preorder + inorder	Recursion + index map	105
Validate BST	Inorder traversal OR range	98
K-th smallest in BST	Inorder traversal	230
LCA in BST	Use BST property (split point)	235

---

The Decision Tree

TREE PROBLEM
│
├─ BST-specific?
│   ├─ Sorted iteration       → Inorder (LC 98, 230)
│   ├─ LCA                    → Split by value (LC 235)
│   └─ Insert / delete        → Standard BST ops
│
├─ Level / shortest path / view from a side?
│   └─ BFS with `for size loop` → LC 102, 107, 199, 637
│
├─ Path / aggregate over root-to-leaf or any-to-any?
│   ├─ Root → leaf sum         → DFS with running sum
│   └─ Any path max sum        → DFS post-order + global max (LC 124)
│
├─ Compare / mirror / clone?
│   └─ Simultaneous DFS (LC 100, 226, 572)
│
├─ Reconstruct from traversals?
│   └─ Recursion + HashMap of inorder index (LC 105)
│
└─ Serialize / deserialize?
    └─ Preorder with "null" tokens (LC 297)

---

The Two Foundational Traversal Templates

DFS (Post-order — most common for “compute & propagate up”)

int dfs(TreeNode node) {
    if (node == null) return 0;
    int left = dfs(node.left);
    int right = dfs(node.right);
    // combine left + right + node.val into the answer
    return 1 + Math.max(left, right);  // example: height
}

BFS (Level Order with size loop)

List<List<Integer>> levels = new ArrayList<>();
if (root == null) return levels;
Queue<TreeNode> q = new ArrayDeque<>();
q.offer(root);
while (!q.isEmpty()) {
    int size = q.size();
    List<Integer> level = new ArrayList<>();
    for (int i = 0; i < size; i++) {
        TreeNode n = q.poll();
        level.add(n.val);
        if (n.left != null)  q.offer(n.left);
        if (n.right != null) q.offer(n.right);
    }
    levels.add(level);
}

Inorder Iterator (for BST)

Deque<TreeNode> stack = new ArrayDeque<>();
TreeNode curr = root;
while (curr != null || !stack.isEmpty()) {
    while (curr != null) { stack.push(curr); curr = curr.left; }
    curr = stack.pop();
    visit(curr);                  // inorder visit
    curr = curr.right;
}

---

Bread & Butter Problems

#	Problem	LC #	Difficulty	Sub-Pattern
1	Maximum Depth of Binary Tree	104	Easy	DFS post-order
2	Same Tree	100	Easy	DFS simultaneous
3	Invert Binary Tree	226	Easy	DFS swap children
4	Binary Tree Level Order Traversal	102	Medium	BFS + size loop
5	Subtree of Another Tree	572	Easy	DFS + sameTree
6	Lowest Common Ancestor of BST	235	Medium	BST split

FAANG “Aha!” Problems

#	Problem	LC #	Difficulty	Sub-Pattern
1	Binary Tree Maximum Path Sum	124	Hard	DFS + global max
2	Serialize and Deserialize Binary Tree	297	Hard	Preorder + null
3	Construct from Preorder and Inorder	105	Medium	Index map + rec
4	Validate Binary Search Tree	98	Medium	Range check / inorder
5	Kth Smallest Element in BST	230	Medium	Inorder + counter

---

Java Implementation Tips

• TreeNode class is never imported on LeetCode — you must reference it as if globally defined.
• For “global tracker” in DFS, prefer int[1] mutable array over instance field (cleaner for sub-functions).
• BFS: use ArrayDeque<TreeNode> not LinkedList — faster, but ArrayDeque forbids nulls, so check before offer.
• For LCA: in a BST use the value-split trick; in a general tree, recursively look for p and q and return the first node where both sides return non-null.
• Recursion depth: skewed trees of 10^4 nodes may stack-overflow — iterative BFS/DFS is safer.

---

Senior Mental Trigger

“Tree problem → recursion. Level info → BFS with size loop. BST → inorder gives sorted order. Path-sum-style → DFS that returns the best path ending at the node, while updating a global max.”