Trees

Three tree types show up in interviews:

• Binary tree — each node has at most a left and right child.
• BST (Binary Search Tree) — binary tree where left < root < right at every node. The sorted property lets you prune entire subtrees, giving O(log n) search and insert.
• N-ary tree — each node has a list of children (file systems, org charts).

All three use DFS or BFS — the traversal logic is the same, only the node structure differs.

Quick Revision - Must Do Problems

If short on time, solve only these. They cover ~90% of tree patterns.

Practice Tips

How to Identify a Tree Problem

• Input is a TreeNode root, or the problem mentions paths, depth, height, or structural comparison
• BST specifically: sorted property, kth element, validation, or LCA

BFS vs DFS

Interview Approach

1. Confirm input type: is the tree a BST or a general binary tree?
2. Choose traversal: BFS for level-order or minimum depth, DFS for everything else
3. Write the recursive base case first (if (root == null) return ...)
4. For bottom-up DFS: compute left and right results first, then combine at the current node
5. For global state (max path sum, diameter): use an instance variable and update it inside the DFS

4 Main Patterns

Pattern 1: Tree DFS (Recursive)

Pre/in/post-order are DFS-only — the only difference is when you process the current node relative to its children.

Preorder — Root → Left → Right (top-down)

Process the current node first, then recurse into children.

Copy    1
   / \
  2   3
Preorder visits: 1, 2, 3

Use when you need to know the parent before visiting children — serializing a tree, copying a tree, building a path top-down.

Copyvoid preorder(TreeNode root) {
    if (root == null) {
        return;
    }
    process(root);          // root first
    preorder(root.left);
    preorder(root.right);
}

Inorder — Left → Root → Right

Go all the way left first, process the node, then go right.

Copy    1
   / \
  2   3
Inorder visits: 2, 1, 3

Use with BSTs — inorder traversal produces values in sorted ascending order. That's the key BST property.

Copyvoid inorder(TreeNode root) {
    if (root == null) {
        return;
    }
    inorder(root.left);
    process(root);          // root in the middle = sorted order for BST
    inorder(root.right);
}

Postorder — Left → Right → Root (bottom-up)

Process both children first, then the current node last.

Copy    1
   / \
  2   3
Postorder visits: 2, 3, 1

Use when you need child results before you can compute the parent — max depth, path sum, any problem where you combine answers from left and right subtrees.

Copyint postorder(TreeNode root) {
    if (root == null) {
        return 0;           // base case
    }
    int left  = postorder(root.left);
    int right = postorder(root.right);
    return process(root.val, left, right); // root last — combine children
}

The mental model — where do you put the "do work here" line?

Copyvoid dfs(TreeNode node) {
    // PREORDER:  do work here
    dfs(node.left);
    // INORDER:   do work here
    dfs(node.right);
    // POSTORDER: do work here
}

Problems in this file: Maximum Depth, Invert Binary Tree, Subtree of Another Tree, Construct from Pre+Inorder, Serialize and Deserialize

Pattern 2: Tree BFS (Level Order)

BFS has no ordering variants — it always visits nodes level by level, left to right.

Copy// Capture queue size before each level — that's how many nodes are on this level
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
    int size = queue.size();            // freeze level size
    for (int i = 0; i < size; i++) {
        TreeNode node = queue.poll();
        process(node);
        if (node.left  != null) {
            queue.offer(node.left);
        }
        if (node.right != null) {
            queue.offer(node.right);
        }
    }
}

Problems in this file: Binary Tree Level Order Traversal, Binary Tree Right Side View

Pattern 3: BST-Specific DFS

Because left < root < right at every node, you can skip an entire subtree the moment the target is out of range — no need to visit every node.

Copypublic void bstDFS(TreeNode root) {
    if (root == null) {
        return;
    }
    if (target < root.val) {
        bstDFS(root.left);   // go left only
    }
    else if (target > root.val) {
        bstDFS(root.right); // go right only
    }
    else {
        process(root);       // found
    }
}

Problems in this file: Validate BST, Lowest Common Ancestor of BST, Kth Smallest in BST

Pattern 4: DFS with Global State

Use when the answer can span both subtrees — forming a "V" through a node — so it can't be passed up through return values alone. The return value carries the best single-direction chain upward; a global variable tracks the best answer seen across the whole tree.

Copyprivate int best = Integer.MIN_VALUE;

private int dfs(TreeNode node) {
    if (node == null) {
        return 0;
    }
    int left  = Math.max(dfs(node.left),  0); // drop negatives
    int right = Math.max(dfs(node.right), 0);
    best = Math.max(best, node.val + left + right); // path through node (both sides)
    return node.val + Math.max(left, right);        // chain upward (one side only)
}

Problems in this file: Binary Tree Maximum Path Sum

Note — Binary Tree vs N-ary Tree

All patterns above assume a binary tree: each node has exactly a left and right child. If the problem gives you an N-ary tree (each node has a list of children — e.g. a file system, org chart, or JSON tree), the logic is identical but you loop over children instead of branching left/right.

N-ary DFS:

Copyvoid dfs(Node root) {
    if (root == null) {
        return;
    }
    process(root);
    for (Node child : root.children) {
        dfs(child);
    }
}

N-ary BFS (level order):

CopyQueue<Node> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
    int size = queue.size();
    for (int i = 0; i < size; i++) {
        Node node = queue.poll();
        process(node);
        for (Node child : node.children) {
            queue.offer(child);
        }
    }
}

General Templates

Data Structure Definition

Copy// Binary tree node
public class TreeNode {
    int val; TreeNode left, right;
    TreeNode(int val) { this.val = val; }
}

// N-ary tree node
public class Node {
    int val;
    List<Node> children;
    Node(int val) { this.val = val; this.children = new ArrayList<>(); }
}

Problem 1: Maximum Depth of Binary Tree ⭐ MUST DO [B75-104]

Return the maximum depth (number of nodes along the longest root-to-leaf path).

Example:

CopyInput:  [3, 9, 20, null, null, 15, 7]
         3
        / \
       9  20
          / \
         15   7
Output: 3

Solution:

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

Complexity:

Real World: A JSON config parser enforcing nesting depth limits — throw an error if any object is nested deeper than a threshold. Also used in rendering collapsible folder trees in IDEs to decide how many levels to expand by default.

Variations:

1. Minimum Depth — use BFS, not DFS. BFS finds the first leaf naturally (level by level) and stops. With DFS, Math.min on a null child returns 0 and incorrectly treats it as a leaf.

   Copyint minDepth(TreeNode root) {
       if (root == null) {
           return 0;
       }
       Queue<TreeNode> queue = new LinkedList<>();
       queue.offer(root);
       int depth = 1;
       while (!queue.isEmpty()) {
           int size = queue.size();
           for (int i = 0; i < size; i++) {
               TreeNode node = queue.poll();
               if (node.left == null && node.right == null) {
                   return depth;          // first leaf found = minimum depth
               }
               if (node.left  != null) { queue.offer(node.left);  }
               if (node.right != null) { queue.offer(node.right); }
           }
           depth++;
       }
       return depth;
   }

Interview Disguises:

• "A comment thread is stored as a tree where each reply is a child node. What is the deepest level of nesting in the thread?" — same as max depth; the tree is just a comment graph instead of a TreeNode.
• "Given a corporate org chart, how many management layers exist between the CEO and the most junior employee?" — longest root-to-leaf path in a tree = max depth.

Problem 2: Invert Binary Tree [B75-226]

Invert a binary tree (mirror it left-to-right).

Example:

CopyInput:        Output:
    4             4
   / \           / \
  2   7    →    7   2
 / \ / \       / \ / \
1  3 6  9     9  6 3  1

Solution:

Copypublic TreeNode invertTree(TreeNode root) {
    if (root == null) {
        return null;
    }
    TreeNode tmp   = root.left;
    root.left      = invertTree(root.right);
    root.right     = invertTree(tmp);
    return root;
}

Complexity:

Real World: Mirroring a tournament bracket for right-to-left display on a scoreboard. Also used in rendering a mirrored org chart when the same hierarchy needs to be shown from right-to-left for RTL language UIs.

Variations:

1. Invert only even levels — swap children only at levels 0, 2, 4, … Use BFS and toggle a boolean each level to decide whether to swap.

Interview Disguises:

• "A tournament bracket is stored as a binary tree. Produce a mirrored version of the bracket for the right-to-left display on the other side of a scoreboard." — mirroring = inverting the tree.
• "An RTL (right-to-left) UI needs to display a navigation menu that is the mirror image of the LTR version stored in memory. Transform the tree in place." — swap left and right children at every node = invert.

Problem 3: Binary Tree Level Order Traversal ⭐ MUST DO [B75-102]

Return the level-order traversal of node values as a list of lists (one per level).

Example:

CopyInput:  [3, 9, 20, null, null, 15, 7]
Output: [[3], [9, 20], [15, 7]]

Key Insight:

• Capture queue.size() before the inner loop — this freezes the number of nodes on the current level before children are added for the next level.

Solution:

Copypublic List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> result = new ArrayList<>();
    if (root == null) {
        return result;
    }

    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);

    while (!queue.isEmpty()) {
        int size = queue.size();                    // freeze level size
        List<Integer> level = new ArrayList<>();
        for (int i = 0; i < size; i++) {
            TreeNode node = queue.poll();
            level.add(node.val);
            if (node.left  != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
        }
        result.add(level);
    }
    return result;
}

Complexity:

Real World: Printing an org chart tier by tier — all C-suite on level 1, all VPs on level 2, all directors on level 3. Also used in BFS web crawlers that process pages grouped by link depth.

Variations:

1. Zigzag Level Order — alternate direction each level: left-to-right on even levels, right-to-left on odd levels. Use a Deque instead of a list per level; add to front or back based on the level parity.
2. Average of levels — return a list of the average value of nodes at each level. Same BFS template; replace level list with a running sum and divide by size at the end of each level.

Interview Disguises:

• "Print all employees in an org chart grouped by their distance from the CEO, one group per line." — grouped-by-depth output = level order traversal.
• "A web crawler discovers pages by following links. Return all URLs found, grouped by how many clicks away they are from the start page." — BFS by depth layer = level order.

Problem 4: Binary Tree Right Side View

Return the values of nodes visible from the right side (the rightmost node at each level).

Example:

CopyInput:  [1, 2, 3, null, 5, null, 4]
Output: [1, 3, 4]

Input:  [1, 2, 3, 4]        ← node 4 is the only node at level 3
Output: [1, 3, 4]

Key Insight:

• BFS naturally groups by level. The last node polled in each level iteration is the rightmost visible node.

Solution:

Copypublic List<Integer> rightSideView(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    if (root == null) {
        return result;
    }

    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);

    while (!queue.isEmpty()) {
        int size = queue.size();
        for (int i = 0; i < size; i++) {
            TreeNode node = queue.poll();
            if (i == size - 1) {
                result.add(node.val); // rightmost on this level
            }
            if (node.left  != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
        }
    }
    return result;
}

Complexity:

Real World: What folders are visible in a collapsed file-tree sidebar when the tree is partially expanded — only the rightmost branch at each depth is visible. Also used in game dev for rendering only the rightmost node in a scene graph level.

Variations:

1. Left Side View — same approach, capture the first node polled per level (i == 0) instead of the last.
2. Both side views merged — return all nodes visible from either side. Combine first and last node per level; deduplicate when a level has only one node.

Interview Disguises:

• "In a company hierarchy, which employees would be visible if you could only look at the org chart from the right side?" — rightmost node at each depth = right side view.

Problem 5: Subtree of Another Tree ⭐ MUST DO [B75-572]

Return true if subRoot is a subtree of root (some node in root has the same structure and values as subRoot).

Example:

CopyInput:  root = [3,4,5,1,2],  subRoot = [4,1,2]  →  true
Input:  root = [3,4,5,1,2,null,null,null,null,0],  subRoot = [4,1,2]  →  false

Key Insight:

• At every node in root, run isSameTree — check if the subtree rooted there is structurally identical to subRoot. Same Tree (LC 100) becomes a helper here, which is why its solution is included inline below.

Solution:

Copypublic boolean isSubtree(TreeNode root, TreeNode subRoot) {
    if (root == null) {
        return false;
    }
    if (isSameTree(root, subRoot)) {
        return true;
    }
    return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);
}

private boolean isSameTree(TreeNode p, TreeNode q) {
    if (p == null && q == null) {
        return true;
    }
    if (p == null || q == null) {
        return false;
    }
    return p.val == q.val
        && isSameTree(p.left,  q.left)
        && isSameTree(p.right, q.right);
}

Complexity:

Real World: Checking if a specific React component subtree exists inside the full rendered component tree — used in UI testing frameworks like Enzyme. Also used in XML/HTML processing to find if a template fragment appears inside a larger document.

Variations:

1. Count occurrences — how many times does subRoot appear as a subtree in root? Remove the early return and accumulate a count instead of returning true on first match.
2. Largest BST subtree — find the largest subtree (by node count) that is itself a valid BST. Bottom-up DFS: each call returns (isBST, min, max, size); propagate upward and track the global max size.

Interview Disguises:

• "You have a large HTML DOM tree and a smaller component template. Check whether that exact template structure appears anywhere inside the full DOM." — checking if a smaller tree exists within a larger one = isSubtree.
• "A file system has thousands of directories. Does a specific folder structure (with exact subfolder names) exist anywhere under the root?" — matching a subtree pattern anywhere in a larger tree = isSubtree.

Problem 6: Validate Binary Search Tree ⭐ MUST DO [B75-98]

Determine if a binary tree is a valid BST (left < root < right at every node).

Example:

CopyInput:  [5, 1, 4, null, null, 3, 6]  →  false  (4 is in right but 4 < 5)
Input:  [2, 1, 3]  →  true

Key Insight:

• Comparing only with the immediate parent is wrong. In the first example, node 3 is in the right subtree of 5 but 3 < 5 — the immediate parent (4) doesn't catch this.
• Pass down a (min, max) boundary at each recursive call. Every node must satisfy min < node.val < max.

Solution:

Copypublic boolean isValidBST(TreeNode root) {
    return validate(root, null, null);
}

private boolean validate(TreeNode node, Integer min, Integer max) {
    if (node == null) {
        return true;
    }
    if (min != null && node.val <= min) {
        return false;
    }
    if (max != null && node.val >= max) {
        return false;
    }
    return validate(node.left,  min,       node.val)
        && validate(node.right, node.val,  max);
}

Complexity:

Real World: Verifying that a database B-tree index is uncorrupted after a crash — every key in the left child must be strictly less than the parent, and every key in the right child strictly greater. A corrupted index would silently return wrong query results.

Variations:

1. Recover BST — exactly two nodes in the BST are swapped by mistake; restore the tree without changing structure. In-order traversal reveals two violations; swap the values of the first and last offending nodes.
2. Convert sorted array to balanced BST — given a sorted array, build a height-balanced BST. Pick the middle element as root, recurse on left and right halves. Inverse of in-order traversal.

Interview Disguises:

• "After a crash recovery, a database index stored as a binary tree may be corrupted. Write a function to verify that every node is strictly greater than all nodes in its left subtree and strictly less than all nodes in its right subtree." — BST invariant check = validate BST with (min, max) bounds.

Problem 7: Lowest Common Ancestor of BST ⭐ MUST DO [B75-235]

Find the lowest common ancestor of two nodes p and q in a BST.

Example:

CopyInput:  root = [6,2,8,0,4,7,9],  p = 2,  q = 8  →  6
Input:  root = [6,2,8,0,4,7,9],  p = 2,  q = 4  →  2

Key Insight:

• BST property makes this O(h) instead of O(n). If both p and q are less than root, LCA is in the left subtree. If both are greater, it's in the right subtree. Otherwise root is the split point — that's the LCA.

Solution:

Copypublic TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    while (root != null) {
        if (p.val < root.val && q.val < root.val) {
            root = root.left;
        }
        else if (p.val > root.val && q.val > root.val) {
            root = root.right;
        }
        else {
            return root; // split point or one of them equals root
        }
    }
    return null;
}

Complexity:

Real World: Finding the nearest common manager of two employees in a company org chart stored as a BST (keyed by employee ID). Used in HR systems to determine approval chains — the LCA is the first person who has authority over both.

Variations:

1. LCA of a general binary tree (not BST) — you cannot use the BST split trick. Use postorder DFS: if both p and q are found in different subtrees of a node, that node is the LCA. LeetCode 236.
2. LCA of multiple nodes — find the LCA of a set of k nodes. Repeatedly apply pairwise LCA, or use a single DFS that counts how many target nodes are in each subtree.

Interview Disguises:

• "In an org chart stored as a BST by employee ID, find the lowest-level manager who has both employee A and employee B in their reporting chain." — LCA = first node where the two targets split to different subtrees.

Problem 8: Kth Smallest Element in a BST ⭐ MUST DO [B75-230]

Return the kth smallest value in a BST.

Example:

CopyInput:  root = [3,1,4,null,2],  k = 1  →  1
Input:  root = [5,3,6,2,4,null,null,1],  k = 3  →  3

Key Insight:

• In-order traversal of a BST yields values in sorted (ascending) order. Stop and return as soon as you've visited k nodes — no need to traverse the full tree.

Solution:

Copyprivate int count = 0, result = 0;

public int kthSmallest(TreeNode root, int k) {
    inorder(root, k);
    return result;
}

private void inorder(TreeNode node, int k) {
    if (node == null) {
        return;
    }
    inorder(node.left, k);
    if (++count == k) {
        result = node.val; return;
    }
    inorder(node.right, k);
}

Complexity:

Real World: Finding the kth cheapest product in a price-indexed catalog without loading all products into memory. Used in leaderboard systems — "who is the kth ranked player?" — where data is stored in a sorted tree.

Variations:

1. Kth Largest — reverse the in-order traversal direction: go right first, then root, then left. Count down from k and return when count reaches k.
2. Frequent kth queries on a mutable BST — if the tree is updated frequently and kth is queried often, augment each node with a leftSize count. Then kth becomes O(log n) by comparing k with leftSize at each node to decide which subtree to descend into.

Interview Disguises:

• "A product catalog is stored as a BST ordered by price. Return the 3rd cheapest item without loading all products into memory." — kth smallest in BST = in-order traversal stopped at k.

Problem 9: Construct Binary Tree from Preorder and Inorder Traversal ⭐ MUST DO [B75-105]

Build a binary tree from its preorder and inorder traversal arrays.

Example:

CopyInput:  preorder = [3,9,20,15,7],  inorder = [9,3,15,20,7]
Output: [3,9,20,null,null,15,7]

Key Insight:

• The first element of preorder is always the root. Find its position in inorder — everything to its left belongs to the left subtree, everything to its right belongs to the right subtree.
• Use a HashMap for O(1) lookup of root positions in inorder. Without it, each lookup is O(n) making the whole algorithm O(n²).

Solution:

Copy/**
 * Reconstruct binary tree from preorder and inorder traversals.
 *
 * KEY INSIGHT:
 *   preorder: root is always FIRST  → tells us WHAT the root is
 *   inorder:  root SPLITS the array → tells us HOW MANY nodes are in left/right subtree
 *
 * BRIDGE BETWEEN THE TWO ARRAYS:
 *   leftSize = inRoot - inL  (calculated from inorder)
 *   then used to slice preorder into left/right windows
 *
 * e.g. preorder=[3,9,20,15,7]  inorder=[9,3,15,20,7]
 *   root=3, inRoot=1, leftSize=1
 *   inorder  → left=[9]    right=[15,20,7]
 *   preorder → left=[9]    right=[20,15,7]
 *
 *       3
 *      / \
 *     9  20
 *        / \
 *       15   7
 *
 */
public class BuildTreeFromPreIn {

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        // build map of inorder value -> index for O(1) root lookup
        // e.g. {9:0, 3:1, 15:2, 20:3, 7:4}
        Map<Integer, Integer> inorderMap = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) {
            inorderMap.put(inorder[i], i);
        }
        return build(preorder, 0, preorder.length - 1, 0, inorder.length - 1, inorderMap);
    }

    private TreeNode build(int[] pre, int preL, int preR, int inL, int inR,
                           Map<Integer, Integer> inorderMap) {

        if (preL > preR) return null;   // empty window, no node to build

        int rootVal  = pre[preL];               // root is always first in preorder window
        int inRoot   = inorderMap.get(rootVal); // find root in inorder → splits left and right
        int leftSize = inRoot - inL;            // number of nodes in left subtree

        TreeNode root = new TreeNode(rootVal);

        // left subtree:  preorder [preL+1 ... preL+leftSize]  inorder [inL ... inRoot-1]
        root.left  = build(pre, preL + 1, preL + leftSize, inL, inRoot - 1, inorderMap);

        // right subtree: preorder [preL+leftSize+1 ... preR]  inorder [inRoot+1 ... inR]
        root.right = build(pre, preL + leftSize + 1, preR, inRoot + 1, inR, inorderMap);

        return root;
    }
}

Complexity:

Real World: Reconstructing a compiler's abstract syntax tree from two serialized traversals stored in a debug log. Also used in database query plan reconstruction when the planner logs traversal orders separately.

Variations:

1. Postorder + Inorder — same structure, one difference: root is post[postR] (last) instead of pre[preL] (first). leftSize and the inorder split work identically.

Copypublic class BuildTreeFromPostIn {

    public TreeNode buildTree(int[] postorder, int[] inorder) {
        Map<Integer, Integer> inorderMap = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) {
            inorderMap.put(inorder[i], i);
        }
        return build(postorder, 0, postorder.length - 1, 0, inorder.length - 1, inorderMap);
    }

    private TreeNode build(int[] post, int postL, int postR, int inL, int inR,
                           Map<Integer, Integer> inorderMap) {

        if (postL > postR) {
            return null;
        }

        int rootVal  = post[postR];             // LAST element — only difference from preorder version
        int inRoot   = inorderMap.get(rootVal);
        int leftSize = inRoot - inL;

        TreeNode root = new TreeNode(rootVal);

        // left subtree:  postorder [postL ... postL+leftSize-1]  inorder [inL ... inRoot-1]
        root.left  = build(post, postL, postL + leftSize - 1, inL, inRoot - 1, inorderMap);

        // right subtree: postorder [postL+leftSize ... postR-1]  inorder [inRoot+1 ... inR]
        root.right = build(post, postL + leftSize, postR - 1, inRoot + 1, inR, inorderMap);

        return root;
    }
}

2. Preorder only (BST) — no inorder needed. The BST property determines left/right placement via (min, max) bounds — no HashMap, O(h) space instead of O(n).

Copy/**
 * Reconstruct BST from preorder traversal only.
 *
 * KEY INSIGHT:
 *   In a BST, left < root < right, so each node has a valid (min, max) range.
 *   We use this to determine placement WITHOUT needing inorder.
 *
 * e.g. preorder = [8, 5, 1, 7, 10, 12]
 *
 *   root=8  (min=-inf, max=+inf) ✅
 *   next=5  (min=-inf, max=8)    ✅ goes LEFT  of 8
 *   next=1  (min=-inf, max=5)    ✅ goes LEFT  of 5
 *   next=7  (min=5,    max=8)    ✅ goes RIGHT of 5
 *   next=10 (min=8,    max=+inf) ✅ goes RIGHT of 8
 *   next=12 (min=10,   max=+inf) ✅ goes RIGHT of 10
 *
 *       8
 *      / \
 *     5  10
 *    / \   \
 *   1   7  12
 */
public class BuildBSTFromPreorder {

    private int idx = 0;  // global pointer into preorder array

    public TreeNode bstFromPreorder(int[] preorder) {
        return build(preorder, Integer.MIN_VALUE, Integer.MAX_VALUE);
    }

    private TreeNode build(int[] pre, int min, int max) {
        if (idx == pre.length) {
            return null;  // all nodes processed
        }

        int val = pre[idx];

        if (val <= min || val >= max) {
            return null;  // out of bounds for this subtree — belongs to a higher level
        }

        idx++;
        TreeNode root = new TreeNode(val);
        root.left  = build(pre, min, val); // left child: smaller than current root
        root.right = build(pre, val, max); // right child: larger than current root
        return root;
    }
}

Interview Disguises:

• "A compiler logs two arrays during parsing: the order it first visited each AST node (preorder) and the order it finished evaluating each expression (inorder). Reconstruct the original AST." — two traversal arrays → reconstruct tree = this exact problem.
• "A backup system saved a binary tree in two passes: one top-down left-right, one in sorted evaluation order. Rebuild the original tree from these two logs." — preorder + inorder → build tree; different framing, identical algorithm.

Problem 10: Binary Tree Maximum Path Sum ⭐ MUST DO [B75-124]

Return the maximum path sum in a binary tree. A path connects any two nodes and may not pass through the root.

Example:

CopyInput:  [-10, 9, 20, null, null, 15, 7]
         -10
         /  \
        9   20
           /  \
          15   7
Output: 42   (path 15→20→7)

Input:  [1, 2, 3]  →  6   (path 2→1→3)

Key Insight:

• At each node, the path through it = node.val + leftGain + rightGain. Update the global max with this.
• But when returning to the parent, you can only extend the path through one side (the chain continues). Return node.val + max(leftGain, rightGain).
• Use max(gain, 0) to drop negative subtrees — never include a branch that makes the sum worse.

Solution:

Copyprivate int maxSum = Integer.MIN_VALUE;

public int maxPathSum(TreeNode root) {
    gain(root);
    return maxSum;
}

private int gain(TreeNode node) {
    if (node == null) {
        return 0;
    }
    int leftGain  = Math.max(gain(node.left),  0); // drop negatives
    int rightGain = Math.max(gain(node.right), 0);
    maxSum = Math.max(maxSum, node.val + leftGain + rightGain); // path through node
    return node.val + Math.max(leftGain, rightGain);            // chain upward
}

Complexity:

Real World: Finding the most profitable sequence of upsells through a product decision tree — each node is a product with a profit margin, and the path represents the customer journey. Also used in network routing to find the highest-bandwidth path between two endpoints.

Variations:

1. Max root-to-leaf path sum — the path must start at the root and end at a leaf; it cannot branch. Remove the global variable; return the running sum and check at leaves. Much simpler than the any-to-any version.
2. Return the actual path — instead of just the max sum, return the list of node values forming the max path. Track parent pointers or reconstruct from the DFS by storing the winning branch at each node.

Interview Disguises:

• "A corporate expense tree stores each department's net profit (positive) or loss (negative). Find the sequence of departments — starting and ending anywhere — that maximizes combined profit." — any-to-any path with max sum = this problem; the gain/chain distinction is the key.

Problem 11: Serialize and Deserialize Binary Tree [B75-297]

Design an algorithm to serialize a binary tree to a string and deserialize it back to the original tree.

Example:

CopyInput:  [1, 2, 3, null, null, 4, 5]
Serialized: "1,2,null,null,3,4,null,null,5,null,null,"
Deserialized: same tree

Key Insight:

• Preorder traversal with explicit null markers ("null") is self-describing — the structure of the tree is fully encoded. During deserialization, consume tokens from a queue; when you see "null", return null (no node here).
• The preorder order guarantees that when you deserialize the root, the next tokens are exactly the left and right subtrees in the same preorder format.

Solution:

Copypublic String serialize(TreeNode root) {
    StringBuilder sb = new StringBuilder();
    serDFS(root, sb);
    return sb.toString();
}

private void serDFS(TreeNode node, StringBuilder sb) {
    if (node == null) {
        sb.append("null,"); return;
    }
    sb.append(node.val).append(",");
    serDFS(node.left,  sb);
    serDFS(node.right, sb);
}

public TreeNode deserialize(String data) {
    Queue<String> q = new LinkedList<>(Arrays.asList(data.split(",")));
    return desDFS(q);
}

private TreeNode desDFS(Queue<String> q) {
    String val = q.poll();
    if (val.equals("null")) {
        return null;
    }
    TreeNode node = new TreeNode(Integer.parseInt(val));
    node.left  = desDFS(q);
    node.right = desDFS(q);
    return node;
}

Complexity:

Real World: Persisting a trained decision tree ML model to disk and reloading it for inference without re-training. Also used in distributed systems to send a parsed expression tree (AST) over the wire between a client and a computation server.

Variations:

1. Serialize using BFS instead of DFS — level-order serialization produces a more human-readable format. Use a queue; write "null" for missing children. Deserialization reads level by level, attaching children to each parent node in order.
2. Serialize a BST compactly — for a BST, null markers are not needed in preorder: the BST property alone determines where each value belongs during deserialization. Process preorder tokens and insert each into the correct position using the (min, max) bounds trick from Validate BST.

Interview Disguises:

• "Design a system to checkpoint a trained decision tree model to disk and restore it later for inference without re-training." — persist and restore a tree structure = serialize/deserialize.
• "A client sends a parsed expression tree to a computation server over a REST API as a string payload. How do you encode the tree on the client and reconstruct it exactly on the server?" — wire format for a tree = serialize/deserialize; preorder + null markers is the standard answer.

Quick Reference Table

When to Use Each Pattern

Tree DFS (Recursive)

• Problem involves depth, height, path sums, or structural comparison
• You need to combine results from left and right subtrees at each node
• Bottom-up: compute children first, then process current node (postorder)
• Top-down: pass information down as parameters (preorder)

Tree BFS (Level Order)

• Output is grouped by level, or you need the last/first node per level
• Problem asks for minimum depth (BFS finds shallowest leaf first)
• Right side view, zigzag traversal — anything level-aware

BST-Specific DFS

• Input is a BST — use the sorted property to prune subtrees
• LCA: both left → go left; both right → go right; otherwise root is LCA
• Kth smallest: in-order gives sorted order; count k steps
• Validate: track (min, max) bounds, not just parent comparison

DFS with Global State

• Problem asks for maximum or minimum path sum across any two nodes
• Track a global variable inside the DFS; return only the best single chain to the parent
• Drop negative branches with Math.max(gain, 0) before updating the global max

Common Mistakes to Avoid

Tree DFS Mistakes

1. Missing null base case — every tree DFS must start with if (root == null) return ...; the value returned must match the return type (0 for int, true/false for boolean, null for node)
2. Returning the wrong value from gain() — in Max Path Sum, the global max uses both branches (left + right), but the return value to the parent uses only max(left, right) — these are different things

Tree BFS Mistakes

4. Not freezing level size — int size = queue.size() must be captured before the inner loop; capturing inside the loop gives a changing size as children are added
5. Missing null check on root — BFS starts with queue.offer(root); if root is null, offer(null) causes NullPointerException

BST Mistakes

6. Comparing only with parent — node.val < parent.val is insufficient; a right-subtree node must be greater than all ancestors, not just its parent — always pass (min, max) bounds
7. Using < instead of <= in BST validation — equal values are not allowed; the check must be node.val <= min (invalid) not node.val < min

Tree DFS — Construct from Traversals

8. Not using a HashMap for inorder lookup — linear scan for root index in inorder makes the algorithm O(n²); always build the index map upfront for O(1) lookup
9. Off-by-one in subtree boundaries — the left subtree in preorder spans [preL+1, preL+leftSize]; the right subtree spans [preL+leftSize+1, preR] — double check these bounds

DFS with Global State Mistakes

10. Global variable not reset between test cases — instance variables like maxSum must be initialized inside the public method, not as a class field with a fixed value; LeetCode reuses the same object across test cases