Trees

Trees are hierarchical data structures where every node has at most two children, and DFS or BFS traversal lets you solve path, depth, structural, and ordering problems cleanly without manual iteration.

• Replaces O(n²) brute force comparisons with O(n) recursive traversal that naturally handles all tree shapes
• Two traversal modes: DFS for depth, paths, and structural problems; BFS for level-order and minimum-depth problems
• Reach for it when the input is a TreeNode, the problem mentions paths or depth, or asks for level-by-level output

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
• Problem mentions paths, depth, height, ancestors, or structural comparison
• Problem asks for level-by-level output or minimum depth
• BST problem: sorted property, kth element, validation, 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

5 Main Patterns

Pattern 1: Tree DFS (Recursive)

Copy// Bottom-up: compute left/right results, combine at current node
public int dfs(TreeNode root) {
    if (root == null) {
        return 0;         // base case
    }
    int left  = dfs(root.left);
    int right = dfs(root.right);
    return process(root.val, left, right); // combine
}

Pattern 2: Tree BFS (Level Order)

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);
        }
    }
}

Pattern 3: BST-Specific DFS

Copy// BST property: left < root < right — prune entire subtrees
public 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
    }
}

Pattern 4: Tree Construction

Copy// Preorder: root first, then left, then right
// Inorder: left, then root, then right
// Root = preorder[preL]; find root in inorder to split left/right subtrees
private TreeNode build(int[] pre, int preL, int preR,
                       int inL,  int inR,  Map<Integer, Integer> idx) {
    if (preL > preR) {
        return null;
    }
    int rootVal  = pre[preL];
    int inRoot   = idx.get(rootVal);
    int leftSize = inRoot - inL;
    TreeNode root = new TreeNode(rootVal);
    root.left  = build(pre, preL + 1,            preL + leftSize, inL,       inRoot - 1, idx);
    root.right = build(pre, preL + leftSize + 1, preR,            inRoot + 1, inR,       idx);
    return root;
}

Pattern 5: Tree Path (Global Max)

Copy// Track global max separately from the return value
// Return value = best single chain up to parent
// Global max = best path through current node (can use both sides)
private int maxSum = Integer.MIN_VALUE;

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
}

General Templates

Data Structure Definition

Copypublic class TreeNode {
    int val; TreeNode left, right;
    TreeNode(int val) { this.val = val; }
}

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 — find the shallowest leaf, not the deepest. BFS is safer here: Math.min on a null child returns 0, incorrectly treating it as a leaf. BFS naturally finds the first leaf it encounters.
2. Level with most nodes — return the depth level that has the maximum number of nodes. Extend the level-order BFS template: track maxCount and maxLevel as you iterate each level.

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: Same Tree ⭐ MUST DO [B75-100]

Given roots of two binary trees, return true if they are structurally identical with the same node values.

Example:

CopyInput:  p = [1,2,3],  q = [1,2,3]  →  true
Input:  p = [1,2],    q = [1,null,2]  →  false

Solution:

Copypublic 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: Frontend snapshot testing — compare the rendered DOM tree before and after a code change to detect unintended structural regressions. Also used in config diffing tools to check if two environment configs are structurally identical.

Variations:

1. Leaf-value equality only — two trees are "equivalent" if all their leaves (left to right) have the same values, ignoring internal structure. Collect leaves from both with DFS, compare the two lists.
2. Count differing nodes — instead of true/false, return how many node positions differ between two trees. Replace the boolean short-circuit with an integer accumulator.

Interview Disguises:

• "Two microservices each parse the same config file into an in-memory tree. Write a function to verify both parsed the file identically." — structural + value equality on two trees = same tree.
• "You have before and after snapshots of a React component tree. Did the structure change?" — comparing two DOM trees node by node is exactly isSameTree.

Problem 3: Invert Binary Tree ⭐ MUST DO [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.
2. Invert then validate — after inverting a BST, is the result still a valid BST? Answer: no (left > root > right becomes the rule), which tests understanding of BST ordering. Ask the candidate to prove it with an example.

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 4: 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 5: 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?" — the rightmost node at each depth = right side view.
• "A folder tree is displayed as a collapsible sidebar. When fully collapsed to a single branch, which folder names remain visible at each level?" — last visible node per level = right side view.

Problem 6: 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 of root, check if the subtree rooted there equals subRoot using isSameTree. This reuses the Same Tree problem as a helper — a common pattern of composing DFS helpers.

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 7: Validate Binary Search Tree ⭐ MUST DO [B75-98]

BST ordering rule: left < root < right

Determine if a binary tree is a valid BST.

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. Node 3 in the right subtree of 5 must be > 5, not just > its parent 6.
• 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.
• "A sorted leaderboard is stored as a binary tree for fast lookups. Verify the tree is still correctly ordered after a recent update — no node should violate the ordering property relative to any ancestor." — same BST validation; the key insight is ancestors impose bounds, not just the immediate parent.

Problem 8: 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.
• "A taxonomy tree of species is stored as a BST by taxonomic ID. Find the most specific common classification shared by two species." — LCA in a BST; the split-point logic is identical.

Problem 9: 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.
• "A leaderboard is stored as a BST by score. A user asks for their percentile rank — specifically, find the player with the kth lowest score." — same in-order count-to-k approach.

Problem 10: 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:

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

private TreeNode build(int[] pre, int preL, int preR,
                       int inL,  int inR,  Map<Integer, Integer> idx) {
    if (preL > preR) {
        return null;
    }
    int rootVal  = pre[preL];
    int inRoot   = idx.get(rootVal);
    int leftSize = inRoot - inL;

    TreeNode root = new TreeNode(rootVal);
    root.left  = build(pre, preL + 1,          preL + leftSize, inL,       inRoot - 1, idx);
    root.right = build(pre, preL + leftSize + 1, preR,          inRoot + 1, inR,       idx);
    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. Construct from Postorder and Inorder — same idea, but the root is the last element of postorder (not the first). Split the inorder array the same way; recurse on right subtree first since postorder is left-right-root.
2. Construct BST from Preorder only — for a BST, inorder is not needed because the BST property determines where each element belongs. Process preorder left to right; for each value, it goes into the position where it satisfies the current (min, max) bounds.

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 11: 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:

• "In a network topology tree, each node represents a server with a throughput value. Find the connection path between any two servers that maximizes total throughput." — max sum across any path in a weighted tree = max path sum.
• "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 12: Serialize and Deserialize Binary Tree ⭐ MUST DO [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

Tree Construction

• Given two traversal arrays (preorder + inorder), rebuild the tree
• Preorder first element is always the root; inorder split gives left/right sizes
• Use a HashMap to look up inorder positions in O(1)

Tree Path (Global Max)

• 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. Global variable not reset between test cases — instance variables like maxSum or diameter must be initialized in the public method, not as class fields with a fixed value
3. 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 Construction Mistakes

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