🌳 Demystifying Tree Problems: Mastering Patterns & Problem Archetypes

Tree problems form a big chunk of coding interviews — from FAANG to startups. At first, they feel endless and random. But if you analyze enough, you’ll realize they’re just variations of a few core patterns.

This guide is a comprehensive pattern map for tree problems: how to identify the right approach, apply the template, and recognize common variations.

---

🔑 Pattern 1: Height & Depth Problems

Clue: Keywords like height, depth, diameter, balanced, longest path.
Core Idea: Recursively calculate the height of subtrees. While doing so, also collect other info (diameter, balance, etc.).

Template:

int height(TreeNode root) {
    if (root == null) return 0;
    return 1 + Math.max(height(root.left), height(root.right));
}

Classic Problems:

1. Maximum Depth of Binary Tree (LeetCode 104)

• Directly return height(root).

1. Balanced Binary Tree (LeetCode 110)

• While computing height, also check if left & right differ by > 1.

1. Diameter of Binary Tree (LeetCode 543)

• Track max(leftHeight + rightHeight) while computing heights.

Variations 🚀:

• Longest Univalue Path (nodes with same value).
• Maximum Path Sum (instead of height, track sum).

👉 If you see "longest", "height", or "diameter" → you’re in this pattern.

---

🔑 Pattern 2: Traversal-Based (DFS)

Clue: Problem involves visiting every node in some order.
Core Idea: Use recursion or stack to simulate preorder, inorder, postorder.

Traversal Orders:

• Preorder → Root → Left → Right
• Inorder → Left → Root → Right
• Postorder → Left → Right → Root

Classic Problems:

1. Inorder Traversal (LeetCode 94)

• Recursive or iterative stack solution.

  1. Construct Binary Tree from Preorder & Inorder (LeetCode 105)

• Recursively build left/right using inorder splits.

  1. Flatten Binary Tree to Linked List (LeetCode 114)

• Preorder traversal + pointer rewiring.

Variations 🚀:

• Recover BST (use inorder sorted property).
• Serialize/Deserialize Tree (use preorder with null markers).

👉 If question talks about "construct", "traverse", or "print in order" → traversal pattern.

---

🔑 Pattern 3: Level Order / BFS

Clue: Keywords like levels, distance, layer, nearest, shortest.
Core Idea: Queue-based BFS traversal.

Template:

Queue<TreeNode> q = new LinkedList<>();
q.add(root);
while (!q.isEmpty()) {
    int size = q.size();
    for (int i = 0; i < size; i++) {
        TreeNode node = q.poll();
        // process node
        if (node.left != null) q.add(node.left);
        if (node.right != null) q.add(node.right);
    }
}

Classic Problems:

1. Binary Tree Level Order Traversal (LeetCode 102)

• Collect values per level.

  1. Minimum Depth of Binary Tree (LeetCode 111)

• BFS until first leaf encountered.

  1. Zigzag Level Order Traversal (LeetCode 103)

• Same as level order but alternate reverse.

Variations 🚀:

• Deepest Leaves Sum (track last level).
• Average of Levels in Binary Tree.
• Vertical Order Traversal (modified BFS).

👉 If it mentions "level" or "distance from root" → BFS pattern.

---

🔑 Pattern 4: Lowest Common Ancestor (LCA)

Clue: Keywords like ancestor, relationship between nodes.
Core Idea: Recurse down. If one node lies in left and other in right → current is LCA.

Template:

TreeNode lca(TreeNode root, TreeNode p, TreeNode q) {
    if (root == null || root == p || root == q) return root;
    TreeNode left = lca(root.left, p, q);
    TreeNode right = lca(root.right, p, q);
    return (left != null && right != null) ? root : (left != null ? left : right);
}

Classic Problems:

1. LCA of Binary Tree (LeetCode 236)
2. LCA of BST (LeetCode 235) → use BST property.

Variations 🚀:

• Distance between two nodes.
• Find nodes in path between two given nodes.

👉 If two nodes and "ancestor/relationship" appear → LCA.

---

🔑 Pattern 5: Path-Based Problems

Clue: Words like path, root-to-leaf, sequence, sum.
Core Idea: Use DFS + backtracking.

Template:

void dfs(TreeNode root, List<Integer> path, int sum) {
    if (root == null) return;
    path.add(root.val);

    if (root.left == null && root.right == null) {
        // check sum/path
    }

    dfs(root.left, path, sum);
    dfs(root.right, path, sum);
    path.remove(path.size() - 1);
}

Classic Problems:

1. Path Sum (LeetCode 112)
2. Path Sum II (LeetCode 113) → store actual paths.
3. Binary Tree Paths (LeetCode 257)

Variations 🚀:

• Maximum Path Sum (track best sum globally).
• Longest path with constraints (like same value).

👉 If it talks about root-to-leaf, path sum, or list of paths → path pattern.

---

🔑 Pattern 6: Subtree / Mirror

Clue: Words like same, identical, mirror, subtree, symmetric.
Core Idea: Recursively compare structures.

Classic Problems:

1. Same Tree (LeetCode 100)
2. Symmetric Tree (LeetCode 101)
3. Subtree of Another Tree (LeetCode 572)

👉 If comparing two trees → subtree/mirror.

---

🔑 Pattern 7: BST Property Problems

Clue: Keywords like BST, order, min, max, kth.
Core Idea: Inorder traversal is sorted → leverage it.

Classic Problems:

1. Validate BST (LeetCode 98)

• Ensure min < root < max for all nodes.

  1. Kth Smallest in BST (LeetCode 230)

• Inorder traversal until kth.

  1. Range Sum of BST (LeetCode 938)

👉 If it’s BST → think sorted inorder + binary search.

---

🔑 Pattern 8: Serialization / Construction

Clue: Words like serialize, deserialize, build tree from array/string.
Core Idea: Encode with preorder + null markers or BFS.

Classic Problems:

1. Serialize and Deserialize Binary Tree (LeetCode 297)
2. Construct Binary Tree from Traversals

👉 If tree is converted to/from string/array → serialization pattern.

---

🔑 Pattern 9: Iterative / Morris Traversal

Clue: Words like without recursion, O(1) space.
Core Idea: Morris traversal (threaded binary tree).

Classic Problems:

• Inorder Traversal without stack/recursion.
• Flatten Tree in-place.

---

📌 Master Pattern Map

Pattern	Keywords/Clues	Example Problems
Height/Depth	height, longest, diameter	LeetCode 104, 110, 543
DFS Traversal	preorder, inorder, postorder	LeetCode 94, 105, 114
BFS Traversal	level, distance, shortest	LeetCode 102, 103, 111
LCA	ancestor, relation	LeetCode 236, 235
Path-Based	path, root-to-leaf, sum	LeetCode 112, 113, 257
Subtree/Mirror	same, mirror, subtree	LeetCode 100, 101, 572
BST	BST, min, max, kth	LeetCode 98, 230, 938
Serialization	serialize, construct	LeetCode 297, 105
Morris/Iterative	no recursion, O(1) space	LeetCode 94, 114

---

🎯 Final Takeaway

Tree problems aren’t infinite — they’re finite patterns.
Next time you face a tree question:

1. Look for keywords (height, path, ancestor, level, BST).
2. Map it to a known pattern.
3. Apply the template, tweak for variations.

Once you master these 9 patterns with examples, 90%+ of tree problems will look familiar.