Trees Master Recap — 9 Patterns Cheatsheet for Coding Interviews

Problem Statement

Recap the entire Trees section as a single cheatsheet. Memorize 9 patterns that cover roughly 95 percent of binary tree, BST, and N-ary tree problems asked at FAANG interviews.

Constraints:

Cheatsheet is meant to be skimmed in under 10 minutes the night before an onsite.
Each pattern fits in under 15 lines of code.
Problems are tagged by pattern so you can drill weak areas first.

Input:  74 tree problems (LC 100, 226, 124, 297, ...)
Output: 9 patterns + complexity tables + problem index

Why This Problem Matters

Trees show up in roughly 20 percent of interview rounds at Google, Meta, Amazon, Microsoft, and Apple. Most candidates fail not because tree problems are uniquely hard but because they have not internalized the small set of recurring patterns. This recap exists so you can map any new problem to a known pattern in under 60 seconds.

The Core Insight

Every tree problem reduces to one of three question types: traverse, derive a value, or restructure. Once you classify the problem, the pattern picks itself.

Visual Dry Run

Pattern	Triggers When	Typical Time
DFS preorder/inorder/postorder	Aggregate subtree info	O(n)
BFS level order	Per-level processing or shortest path	O(n)
Tree DP returning tuple	Need two values from each subtree	O(n)
BST bounds	Validate or build BST	O(n)
LCA recursion	Find shared ancestor	O(n)
Path sum prefix counts	Count paths summing to k	O(n)
Serialize/deserialize	Encode tree as string	O(n)
Binary lifting	Repeated kth-ancestor queries	O(n log n) preprocess
Rerooting	Aggregate value for every root	O(n)

Solution (Optimal)

Pattern 1 — DFS three orders.

class Solution:
    def traverse(self, root):
        def dfs(node):
            if not node:
                return
            # preorder action here
            dfs(node.left)
            # inorder action here
            dfs(node.right)
            # postorder action here
        dfs(root)

var traverse = function(root) {
    const dfs = (node) => {
        if (!node) return;
        // preorder action
        dfs(node.left);
        // inorder action
        dfs(node.right);
        // postorder action
    };
    dfs(root);
};

Pattern 2 — BFS level order.

from collections import deque
 
class Solution:
    def levelOrder(self, root):
        if not root:
            return []
        q = deque([root])
        result = []
        while q:
            level = []
            for _ in range(len(q)):
                node = q.popleft()
                level.append(node.val)
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
            result.append(level)
        return result

var levelOrder = function(root) {
    if (!root) return [];
    const q = [root];
    const result = [];
    while (q.length) {
        const level = [];
        const size = q.length;
        for (let i = 0; i < size; i++) {
            const node = q.shift();
            level.push(node.val);
            if (node.left) q.push(node.left);
            if (node.right) q.push(node.right);
        }
        result.push(level);
    }
    return result;
};

Pattern 3 — Tree DP returning a tuple.

class Solution:
    def diameter(self, root):
        self.best = 0
        def dfs(node):
            if not node:
                return 0
            l = dfs(node.left)
            r = dfs(node.right)
            self.best = max(self.best, l + r)
            return 1 + max(l, r)
        dfs(root)
        return self.best

var diameter = function(root) {
    let best = 0;
    const dfs = (node) => {
        if (!node) return 0;
        const l = dfs(node.left);
        const r = dfs(node.right);
        best = Math.max(best, l + r);
        return 1 + Math.max(l, r);
    };
    dfs(root);
    return best;
};

Pattern 4 — BST bounds.

class Solution:
    def isValidBST(self, root):
        def dfs(node, lo, hi):
            if not node:
                return True
            if not (lo < node.val < hi):
                return False
            return dfs(node.left, lo, node.val) and dfs(node.right, node.val, hi)
        return dfs(root, float('-inf'), float('inf'))

var isValidBST = function(root) {
    const dfs = (node, lo, hi) => {
        if (!node) return true;
        if (node.val <= lo || node.val >= hi) return false;
        return dfs(node.left, lo, node.val) && dfs(node.right, node.val, hi);
    };
    return dfs(root, -Infinity, Infinity);
};

Pattern 5 — LCA on a binary tree.

class Solution:
    def lca(self, root, p, q):
        if not root or root is p or root is q:
            return root
        left = self.lca(root.left, p, q)
        right = self.lca(root.right, p, q)
        if left and right:
            return root
        return left or right

var lca = function(root, p, q) {
    if (!root || root === p || root === q) return root;
    const left = lca(root.left, p, q);
    const right = lca(root.right, p, q);
    if (left && right) return root;
    return left || right;
};

Time: O(n) for traversal patterns, O(n log n) for binary lifting preprocess. Space: O(h) recursion stack on average, O(n) worst case for a skewed tree.

Common Mistakes

Trying to track parents in a global dict when a postorder return tuple suffices.
Using BFS when the question wants per-leaf info — DFS is usually cleaner there.
Validating a BST by only comparing parent and child instead of carrying min and max bounds.
Forgetting to reset shared state between test cases when using class-level variables.
Recursing into nulls without a base case, leading to AttributeError or null pointer.

Interview Tips

Out loud, classify the problem into one of the 9 patterns before writing code.
For BST problems, state the inorder property right away — it earns instant credit.
When asked about complexity, mention both balanced and skewed cases.
Ask if the tree fits in memory — for huge trees, mention iterative or Morris traversal.
Mention parent pointers as a structural shortcut whenever the problem allows them.

Follow-up Questions

Iterative inorder: convert recursion to an explicit stack. Hint: simulate the call stack.
Morris traversal: O(1) space inorder. Hint: thread predecessor right pointers.
Parallel BFS: process levels concurrently. Hint: queue per worker, drain with barriers.
Persistent BST: keep all versions cheaply. Hint: path copying.
B-tree generalization: branch factor greater than 2 for disk friendliness.

Key Takeaways

The 9 patterns cover almost every tree problem on LeetCode and FAANG onsites.
Postorder is for collecting subtree info, preorder for passing info down, inorder for BSTs.
BFS shines on level-based and shortest-path tree problems.
Tree DP returning tuples handles diameter, max path sum, and house robber III in one shape.
BST validation always uses min and max bounds, never parent comparison alone.
Serialize and deserialize is just preorder with a sentinel for nulls.
Binary lifting preprocesses ancestors so each query becomes O(log n).

Problem Statement#

Why This Problem Matters#

The Core Insight#

Visual Dry Run#

Solution (Optimal)#

Common Mistakes#

Interview Tips#

Follow-up Questions#

Key Takeaways#

Related reading