DSA Series: Tree, BST and Trie (Blind 75, Java)

Overview

• Pattern cheat-sheet
• TreeNode definition
• 1. Maximum Depth of Binary Tree (Easy · LeetCode #104)
• 2. Same Tree (Easy · LeetCode #100)
• 3. Invert Binary Tree (Easy · LeetCode #226)
• 4. Binary Tree Maximum Path Sum (Hard · LeetCode #124)
• 5. Binary Tree Level Order Traversal (Medium · LeetCode #102)
• 6. Serialize and Deserialize Binary Tree (Hard · LeetCode #297)
• 7. Subtree of Another Tree (Easy · LeetCode #572)
• 8. Construct Binary Tree from Preorder and Inorder Traversal (Medium · LeetCode #105)
• 9. Validate Binary Search Tree (Medium · LeetCode #98)
• 10. Kth Smallest Element in a BST (Medium · LeetCode #230)
• 11. Lowest Common Ancestor of a BST (Medium · LeetCode #235)
• 12. Implement Trie (Prefix Tree) (Medium · LeetCode #208)
• 13. Design Add and Search Words Data Structure (Medium · LeetCode #211)
• 14. Word Search II (Hard · LeetCode #212)

Part of the DSA Blind 75 series. Track your progress on the Interview Prep page.

Target: Visa, Mastercard, NPCI, American Express, PayU. All Java code in this file was compiled with javac and checked with asserts on the examples and edge cases.

Pattern cheat-sheet

Complexities: let n = nodes, h = height. Balanced h = O(log n), skewed h = O(n). Recursive DFS uses O(h) call stack; for skewed trees with n around 10^5 or more, recursion can throw StackOverflowError in Java, so know the iterative version.

TreeNode definition

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

1. Maximum Depth of Binary Tree (Easy · LeetCode #104)

Problem statement. Given the root of a binary tree, return its maximum depth: the number of nodes along the longest path from the root down to the farthest leaf.

• Example: [3,9,20,null,null,15,7] -> 3.
• Example: [1,null,2] -> 2.
• Constraints: nodes in [0, 10^4], -100 <= val <= 100.

How the interviewer asks / follow-ups.

• Fintech disguise: "A transaction approval workflow is modeled as a tree of rules/approvers. What is the longest chain of approvals a request may pass through?" Or "depth of an org/merchant hierarchy (parent merchant -> sub-merchant -> store)".
• Follow-ups: do it iteratively (BFS counting levels, or DFS with explicit stack storing depth); what if the tree is skewed with 10^6 nodes (stack overflow risk)? Min depth variant (careful with a node that has one child). N-ary tree version.
• Evaluating: comfort with base case and recursion, understanding of recursion stack cost, and ability to switch to BFS.

Approach 1: Brute force. There is no meaningfully slower approach; a "brute" version collects every root-to-leaf path and takes the longest. Time O(n) (each node visited once) but O(n) extra memory for paths in the worst case. Not worth using.

Approach 2: Recursive DFS (optimal). Intuition: depth(node) = 1 + max(depth(left), depth(right)); depth(null) = 0. Trace on [3,9,20,null,null,15,7]: depth(9)=1, depth(15)=1, depth(7)=1, depth(20)=1+max(1,1)=2, depth(3)=1+max(1,2)=3.

Approach 3: BFS level count. Process level by level; each completed level adds 1. Avoids deep recursion.

Java code.

// Recursive DFS
static int maxDepth(TreeNode root) {
    if (root == null) return 0;                       // empty subtree has depth 0
    return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}

// Iterative BFS: safe for very deep (skewed) trees
static int maxDepthBfs(TreeNode root) {
    if (root == null) return 0;
    int depth = 0;
    Deque<TreeNode> q = new ArrayDeque<>();
    q.add(root);
    while (!q.isEmpty()) {
        for (int i = q.size(); i > 0; i--) {          // drain exactly one level
            TreeNode n = q.poll();
            if (n.left != null) q.add(n.left);
            if (n.right != null) q.add(n.right);
        }
        depth++;
    }
    return depth;
}

Complexity.

• Recursive: Time O(n), every node visited once. Space O(h) recursion stack (O(n) skewed, O(log n) balanced).
• BFS: Time O(n). Space O(w) where w is the max level width (up to about n/2 for a complete tree).

Edge cases / pitfalls. Null root returns 0. Skewed tree: recursion depth equals n, so mention StackOverflowError and offer BFS. Don't confuse depth in nodes vs edges (LeetCode counts nodes). For min depth, a node with one null child is not a leaf, so don't take min(0, x).

Pattern & related. Basic post-order recursion (combine children). Related: Minimum Depth (#111), Balanced Binary Tree (#110), Diameter of Binary Tree (#543), Maximum Depth of N-ary Tree (#559).

2. Same Tree (Easy · LeetCode #100)

Problem statement. Given roots p and q, return true if the trees are structurally identical and corresponding nodes hold equal values.

• Example: p=[1,2,3], q=[1,2,3] -> true.
• Example: p=[1,2], q=[1,null,2] -> false (same values, different structure).
• Constraints: nodes in [0, 100], -10^4 <= val <= 10^4.

How the interviewer asks / follow-ups.

• Fintech disguise: "Two rule-engine configurations are stored as decision trees. Verify that the config deployed in production equals the one approved by risk." Or comparing a replicated tree with the primary after a sync.
• Follow-ups: iterative version with two stacks/queues; how to compare large trees cheaply (hash/Merkle-style hashing of subtrees, a precursor to Subtree of Another Tree); mirror-image check (Symmetric Tree #101).
• Evaluating: null handling in three cases (both null, one null, both non-null), short-circuiting.

Approach 1: Brute force. Serialize both trees (with null markers) and compare strings. Time O(n+m), extra space O(n+m). Works, but allocates and cannot exit early.

Approach 2: Parallel DFS (optimal). Intuition: two trees are the same iff roots match and left subtrees match and right subtrees match. Trace [1,2] vs [1,null,2]: roots 1==1; left: node 2 vs null -> exactly one is null -> false.

Java code.

static boolean isSameTree(TreeNode p, TreeNode q) {
    if (p == null || q == null) return p == q;        // true only if both are null
    return p.val == q.val
        && isSameTree(p.left, q.left)                 // && short-circuits on first mismatch
        && isSameTree(p.right, q.right);
}

Complexity.

• Brute (serialize): Time O(n+m), Space O(n+m).
• Parallel DFS: Time O(min(n, m)) since it stops at the first mismatch (O(n) worst). Space O(h) recursion stack.

Edge cases / pitfalls. Both null -> true. One null -> false. Compare values with == on int (if the node held Integer, use .equals, since == on boxed values outside -128..127 compares references). Structure matters, not just inorder values.

Pattern & related. Parallel recursion on two trees. Related: Subtree of Another Tree (#572), Symmetric Tree (#101), Merge Two Binary Trees (#617).

3. Invert Binary Tree (Easy · LeetCode #226)

Problem statement. Invert a binary tree (mirror it) and return the root.

• Example: [4,2,7,1,3,6,9] -> [4,7,2,9,6,3,1].
• Example: [2,1,3] -> [2,3,1]; [] -> [].
• Constraints: nodes in [0, 100], -100 <= val <= 100.

How the interviewer asks / follow-ups.

• Fintech disguise: "Flip a left/right-oriented ledger tree (e.g., debit/credit view) to its mirrored representation in place." Often asked simply as a warm-up.
• Follow-ups: iterative with stack or queue; do it without extra memory; what is the order (pre/post) and does it matter (it does not, as long as you swap both children).
• Evaluating: clean recursion, avoiding the temp-variable bug.

Approach 1: Brute force. Build a brand-new mirrored tree by copying nodes (new TreeNode(val, mirror(right), mirror(left))). Time O(n), space O(n) extra for the new tree. Fine, but not in place.

Approach 2: In-place recursion (optimal). Intuition: mirror(node) = node with children swapped, each child itself mirrored. Trace [2,1,3]: save left=1; set left = invert(3) = 3; set right = invert(1) = 1 -> [2,3,1].

Approach 3: Iterative. Stack (or queue): pop a node, swap its children, push non-null children.

Java code.

// Recursive, in place
static TreeNode invertTree(TreeNode root) {
    if (root == null) return null;
    TreeNode oldLeft = root.left;                     // save before overwriting
    root.left = invertTree(root.right);
    root.right = invertTree(oldLeft);
    return root;
}

// Iterative, in place
static TreeNode invertTreeIter(TreeNode root) {
    if (root == null) return null;
    Deque<TreeNode> stack = new ArrayDeque<>();
    stack.push(root);
    while (!stack.isEmpty()) {
        TreeNode n = stack.pop();
        TreeNode t = n.left; n.left = n.right; n.right = t;   // swap
        if (n.left != null) stack.push(n.left);
        if (n.right != null) stack.push(n.right);
    }
    return root;
}

Complexity.

• Copy approach: Time O(n), Space O(n) new nodes plus O(h) stack.
• In place recursive: Time O(n), Space O(h) stack.
• Iterative: Time O(n), Space O(h) for a stack on DFS order (O(w) if you use a queue).

Edge cases / pitfalls. Null root. Forgetting to save left before overwriting it (a classic bug that loses the subtree). Don't push null children onto an ArrayDeque (it throws NPE).

Pattern & related. Simple recursion with a structural change. Related: Symmetric Tree (#101), Flip Equivalent Binary Trees (#951), Same Tree (#100).

4. Binary Tree Maximum Path Sum (Hard · LeetCode #124)

Problem statement. A path is a sequence of nodes where each adjacent pair is connected by an edge; each node appears at most once; it need not pass through the root. Return the maximum sum of any non-empty path.

• Example: [1,2,3] -> 6 (2 -> 1 -> 3).
• Example: [-10,9,20,null,null,15,7] -> 42 (15 -> 20 -> 7).
• Constraints: nodes in [1, 3*10^4], -1000 <= val <= 1000.

How the interviewer asks / follow-ups.

• Fintech disguise: "Each node is a settlement/netting step with a positive or negative P&L. Find the contiguous chain through the hierarchy with the largest net gain." Or best-profit route in a fee-routing tree.
• Follow-ups: also return the path itself (track nodes); what if all values are negative; make it iterative (post-order with a map); relation to Diameter of Binary Tree and to Kadane's algorithm.
• Evaluating: separating "what I return to the parent" (a one-armed path) from "what I record as the answer" (a two-armed path through this node).

Approach 1: Brute force. For every node as the "top" of the path, compute the best downward path on the left and on the right separately (a full DFS each time), then combine. Time O(n^2) for a skewed tree (O(n log n) for balanced) because the downward gains are recomputed repeatedly. Space O(h).

Approach 2: Single post-order pass (optimal). Intuition: for each node, gain(node) = best sum of a downward path that starts at this node = val + max(0, gain(left), gain(right)). The best path whose highest node is this one is val + max(0, gain(left)) + max(0, gain(right)). Clamp negative gains to 0 (we simply do not extend into that child). Track the global max. Trace [-10,9,20,null,null,15,7]: gain(9)=9 (best=9); gain(15)=15, gain(7)=7, at 20: through-path 20+15+7=42 (best=42), return 20+15=35; at -10: through-path -10+9+35=34 (<42), return -10+35=25. Answer 42.

Java code.

private int best;

public int maxPathSum(TreeNode root) {
    best = Integer.MIN_VALUE;           // NOT 0: all-negative trees must return the max (negative) node
    gain(root);
    return best;
}

// Returns the max sum of a downward path starting at n (may be extended by the parent).
private int gain(TreeNode n) {
    if (n == null) return 0;
    int l = Math.max(0, gain(n.left));   // drop a negative branch
    int r = Math.max(0, gain(n.right));
    best = Math.max(best, n.val + l + r); // path with n as the topmost node
    return n.val + Math.max(l, r);        // parent can only extend ONE branch
}

Complexity.

• Brute force: Time O(n^2) worst case, Space O(h).
• Optimal: Time O(n), each node visited once. Space O(h) recursion stack.

Edge cases / pitfalls. All-negative tree: initialize best to Integer.MIN_VALUE, not 0 (e.g. [-3] -> -3). Return only one branch to the parent (returning both would make a non-path). The path must contain at least one node. Sum bound: 310^4 * 1000 = 310^7, fits in int; mention using long if values were larger. Use an instance field or int[1] for the global max, not a static shared across test cases.

Pattern & related. Post-order DP on a tree, "return partial, record complete" (like Kadane's). Related: Diameter of Binary Tree (#543), Longest Univalue Path (#687), Path Sum III (#437), House Robber III (#337).

5. Binary Tree Level Order Traversal (Medium · LeetCode #102)

Problem statement. Return the level-order traversal (left to right, level by level) of the node values.

• Example: [3,9,20,null,null,15,7] -> [[3],[9,20],[15,7]].
• Example: [1] -> [[1]]; [] -> [].
• Constraints: nodes in [0, 2000], -1000 <= val <= 1000.

How the interviewer asks / follow-ups.

• Fintech disguise: "Print an org chart / merchant hierarchy level by level" or "process dependent payment-rule groups layer by layer (all of layer k can run in parallel)".
• Follow-ups: zigzag order (#103); right side view (#199); bottom-up (#107); recursive (DFS with a depth parameter) version; memory when the tree is very wide.
• Evaluating: the size() snapshot trick, correct queue usage, handling the empty tree.

Approach 1: Brute force. Compute the height, then for each level d run a DFS collecting nodes at depth d. Time O(n * h) (O(n^2) skewed), Space O(h) plus output.

Approach 2: BFS with a queue (optimal). Intuition: a FIFO queue naturally visits nodes level by level. At the start of each round, q.size() is exactly the number of nodes in the current level. Trace: q=[3] -> level [3], enqueue 9,20 -> level size 2: [9,20], enqueue 15,7 -> level [15,7]. Done.

Approach 3: DFS with depth. dfs(node, depth): if depth == res.size() add a new list; append to res.get(depth). Preorder with left before right preserves left-to-right order. Time O(n), Space O(h).

Java code.

static List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> res = new ArrayList<>();
    if (root == null) return res;
    Queue<TreeNode> q = new ArrayDeque<>();
    q.add(root);
    while (!q.isEmpty()) {
        int size = q.size();                          // snapshot: nodes in this level
        List<Integer> level = new ArrayList<>(size);
        for (int i = 0; i < size; i++) {
            TreeNode n = q.poll();
            level.add(n.val);
            if (n.left != null) q.add(n.left);
            if (n.right != null) q.add(n.right);
        }
        res.add(level);
    }
    return res;
}

Complexity.

• Brute force: Time O(n*h), Space O(h) + output.
• BFS: Time O(n). Space O(w) for the queue, w = max width (up to about n/2), plus O(n) for the output.
• DFS-with-depth: Time O(n), Space O(h) recursion stack plus output.

Edge cases / pitfalls. Empty tree returns an empty list (not [[]]). Do not call q.size() in the loop condition (it changes as you enqueue). ArrayDeque rejects nulls, so only enqueue non-null children.

Pattern & related. BFS level-by-level. Related: Zigzag Level Order (#103), Right Side View (#199), Average of Levels (#637), Minimum Depth (#111), Word Ladder (#127).

6. Serialize and Deserialize Binary Tree (Hard · LeetCode #297)

Problem statement. Design an algorithm to serialize a binary tree to a string and deserialize that string back to the original tree. No format is mandated, but it must round-trip.

• Example: [1,2,3,null,null,4,5] -> some string -> same tree.
• Constraints: nodes in [0, 10^4], -1000 <= val <= 1000.

How the interviewer asks / follow-ups.

• Fintech disguise: "Persist a rule/decision tree to a database column or send it over the wire (Kafka message, REST payload) and rebuild it on another service." Also "cache a merchant-category hierarchy in Redis".
• Follow-ups: why a null marker is needed (inorder alone is ambiguous; preorder + null markers is unique); delimiter choice and negative numbers; BFS (LeetCode-style) vs DFS format; compact binary encoding; for a BST, preorder alone is enough (no nulls) via bounds; handle values that could contain the delimiter; schema versioning; very deep tree -> iterative.
• Evaluating: encoding design, symmetry between the two functions, and correctness around nulls and delimiters.

Approach 1: Brute force / naive. Store inorder and preorder traversals and rebuild with the "Construct from Preorder and Inorder" algorithm. Requires unique values (fails with duplicates) and doubles the payload. Time O(n), Space O(n). Not general.

Approach 2: Preorder DFS with null markers (optimal, simple). Intuition: preorder with explicit # for null children uniquely identifies the tree, since reading the stream you know exactly when each subtree ends. Trace [1,2,3,null,null,4,5]: serialize -> 1,2,#,#,3,4,#,#,5,#,#,. Deserialize: read 1 -> build left: read 2 -> left # null, right # null -> back to 1's right: 3 -> left 4 (#,#), right 5 (#,#).

Approach 3: BFS (level order) with null markers. Same format LeetCode uses; queue-based, avoids deep recursion, good for skewed trees.

Java code.

public class Codec {
    private static final String NULL = "#";
    private static final String SEP = ",";

    // ---------- DFS (preorder) ----------
    public String serialize(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        write(root, sb);
        return sb.toString();
    }
    private void write(TreeNode n, StringBuilder sb) {
        if (n == null) { sb.append(NULL).append(SEP); return; }
        sb.append(n.val).append(SEP);
        write(n.left, sb);
        write(n.right, sb);
    }

    public TreeNode deserialize(String data) {
        Deque<String> tokens = new ArrayDeque<>(Arrays.asList(data.split(SEP)));
        return read(tokens);
    }
    private TreeNode read(Deque<String> tokens) {
        String t = tokens.poll();
        if (t.equals(NULL)) return null;
        TreeNode n = new TreeNode(Integer.parseInt(t));   // handles negatives
        n.left = read(tokens);                            // same order as write()
        n.right = read(tokens);
        return n;
    }

    // ---------- BFS (level order), iterative ----------
    public String serializeBfs(TreeNode root) {
        if (root == null) return "";
        StringBuilder sb = new StringBuilder();
        Queue<TreeNode> q = new LinkedList<>();           // LinkedList: allows null elements
        q.add(root);
        while (!q.isEmpty()) {
            TreeNode n = q.poll();
            if (n == null) { sb.append(NULL).append(SEP); continue; }
            sb.append(n.val).append(SEP);
            q.add(n.left);
            q.add(n.right);
        }
        return sb.toString();
    }

    public TreeNode deserializeBfs(String data) {
        if (data.isEmpty()) return null;
        String[] p = data.split(SEP);
        TreeNode root = new TreeNode(Integer.parseInt(p[0]));
        Queue<TreeNode> q = new ArrayDeque<>();
        q.add(root);
        int i = 1;
        while (!q.isEmpty() && i < p.length) {
            TreeNode n = q.poll();
            if (!p[i].equals(NULL)) { n.left = new TreeNode(Integer.parseInt(p[i])); q.add(n.left); }
            i++;
            if (i < p.length && !p[i].equals(NULL)) { n.right = new TreeNode(Integer.parseInt(p[i])); q.add(n.right); }
            i++;
        }
        return root;
    }
}

(Tested round trips on: empty tree, single node, skewed, full, and Integer.MIN_VALUE/MAX_VALUE values.)

Complexity.

• Preorder-pair brute force: Time O(n), Space O(n), duplicates unsupported.
• DFS format: Time O(n) for both directions; Space O(n) for the string/tokens plus O(h) recursion stack.
• BFS format: Time O(n); Space O(n) string plus O(w) queue.
• Note: string appends use StringBuilder (never += in a loop, which is O(n^2)).

Edge cases / pitfalls. Empty tree (serialize to "" in BFS or "#," in DFS; make sure deserialize handles it: "#,".split(",") gives ["#"], fine). Negative numbers: the - sign is not a delimiter. Values containing the delimiter (use length-prefixing or a binary format if values are strings). ArrayDeque throws NPE on null, so the BFS serializer uses LinkedList. Do not rely on inorder alone. Trailing delimiter is harmless because String.split drops trailing empty strings.

Pattern & related. Tree <-> linear encoding via traversal with sentinel for null. Related: Construct BT from Preorder and Inorder (#105), Serialize and Deserialize BST (#449), Encode and Decode N-ary Tree (#428), Find Duplicate Subtrees (#652; serialization as a hash key).

7. Subtree of Another Tree (Easy · LeetCode #572)

Problem statement. Given roots root and subRoot, return true if some subtree of root (a node plus all of its descendants) has the same structure and values as subRoot.

• Example: root=[3,4,5,1,2], subRoot=[4,1,2] -> true.
• Example: root=[3,4,5,1,2,null,null,null,null,0], subRoot=[4,1,2] -> false.
• Constraints: root nodes in [1, 2000], subRoot nodes in [1, 1000], values in [-10^4, 10^4].

How the interviewer asks / follow-ups.

• Fintech disguise: "Does a fraud pattern (small decision tree) appear anywhere inside the large rule tree?" or "Is this approved sub-hierarchy contained in the merchant hierarchy?"
• Follow-ups: can you do better than O(m*n) (serialize both with markers and use KMP, or Merkle hashing for O(m+n))? Why must the subtree include all descendants down to the leaves? Why a naive string contains can give false positives (12 vs 2; need delimiters and null markers).
• Evaluating: reuse of isSameTree, awareness of the complexity, and string-matching correctness.

Approach 1: Brute force (standard, accepted). For each node of root, run isSameTree(node, subRoot). Time O(n*m), Space O(h).

Approach 2: Serialize + string matching. Serialize both trees in preorder with null markers and a leading delimiter before every value (e.g. ^3,^4,...), then check substring (KMP for guaranteed O(n+m)). Time O(n+m) with KMP, Space O(n+m).

Approach 3: Subtree hashing (Merkle). Compute a canonical id for each subtree in one pass (map of (val, leftId, rightId) -> id); then subRoot is present iff its id appears in root. Time O(n+m), Space O(n+m).

Intuition for the brute force trace: root 3 vs [4,1,2] mismatches, go left; node 4 matches 4, children 1 and 2 match, both null children match -> true. In example 2, node 4 has an extra child 0 under 2 so isSame fails there; no other node equals 4 -> false.

Java code.

static boolean isSubtree(TreeNode root, TreeNode subRoot) {
    if (subRoot == null) return true;                 // empty tree is a subtree of anything
    if (root == null) return false;
    return isSame(root, subRoot)
        || isSubtree(root.left, subRoot)
        || isSubtree(root.right, subRoot);
}

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

Complexity.

• Brute force: Time O(n*m) worst case (e.g. a tree of all-equal values), each of n nodes may start a comparison of up to m nodes. Space O(h) recursion.
• Serialize + KMP: Time O(n+m), Space O(n+m).
• Hashing: Time O(n+m) expected, Space O(n+m).

Edge cases / pitfalls. Must match to the leaves: [4,1,2] is not in a tree where 4 has an extra descendant. Matching only root values is wrong. String approach: without delimiters and null markers you get false positives. Constraint says non-empty, but handle subRoot == null anyway and say so.

Pattern & related. Tree matching using the Same Tree subroutine; tree hashing. Related: Same Tree (#100), Find Duplicate Subtrees (#652), Count Univalue Subtrees (#250).

8. Construct Binary Tree from Preorder and Inorder Traversal (Medium · LeetCode #105)

Problem statement. Given preorder and inorder arrays of the same tree (unique values), construct and return the tree.

• Example: preorder=[3,9,20,15,7], inorder=[9,3,15,20,7] -> [3,9,20,null,null,15,7].
• Example: preorder=[-1], inorder=[-1] -> [-1].
• Constraints: 1 <= n <= 3000, values unique in [-3000, 3000].

How the interviewer asks / follow-ups.

• Fintech disguise: "A tree was exported as two traversal logs by two systems; reconstruct the original hierarchy." Or rebuilding a tree from audit logs.
• Follow-ups: why the pair is unique only with distinct values; can inorder + postorder do it (#106); can preorder + postorder (not unique unless full tree, #889); can you do it with O(1) lookup per node (HashMap); avoid array copying (use index bounds); iterative approach.
• Evaluating: understanding what each traversal tells you (preorder gives the root, inorder splits left/right) and index arithmetic.

Approach 1: Brute force. Take preorder[0] as root, linearly search it in inorder, slice arrays (copy) for left and right, recurse. Time O(n^2) worst case (skewed: linear search at each level) plus copying; Space O(n^2) for copies in the worst case, or O(n) per level.

Approach 2: HashMap + index bounds (optimal). Intuition: preorder visits root, then the whole left subtree, then the right subtree, so a single moving pointer pi into preorder hands out roots in the correct order if we recurse left before right. A map value -> inorder index splits the inorder range in O(1). Trace on the example: pi=0 root 3, inorder index 1, left range [0,0], right range [2,4]. Left: root 9 (pi=1), range [0,0] with idx 0, children ranges empty. Right: root 20 (pi=2), idx 3: left [2,2] -> 15 (pi=3), right [4,4] -> 7 (pi=4).

Java code.

class Solution {
    private Map<Integer, Integer> inIdx;
    private int[] pre;
    private int pi;                                   // next root in preorder

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        pre = preorder;
        pi = 0;
        inIdx = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) inIdx.put(inorder[i], i);
        return build(0, inorder.length - 1);
    }

    private TreeNode build(int lo, int hi) {          // inorder range [lo, hi]
        if (lo > hi) return null;
        TreeNode node = new TreeNode(pre[pi++]);
        int mid = inIdx.get(node.val);
        node.left = build(lo, mid - 1);               // MUST build left before right
        node.right = build(mid + 1, hi);
        return node;
    }
}

Complexity.

• Brute: Time O(n^2), Space O(n^2) worst case due to array copies.
• Optimal: Time O(n) (n map inserts, n lookups, each node built once). Space O(n) for the map plus O(h) recursion stack.

Edge cases / pitfalls. Build left before right, otherwise pi is consumed in the wrong order. Unique values required (state it). Skewed input means recursion depth n (n <= 3000 here, fine). Don't use Arrays.copyOfRange per call. Bad input (arrays of different lengths or inconsistent traversals) would give a NPE from inIdx.get; validate in production code.

Pattern & related. Divide and conquer using traversal properties + hash index. Related: Construct from Inorder and Postorder (#106; consume postorder from the end, build right first), Construct BST from Preorder (#1008), Serialize/Deserialize (#297).

9. Validate Binary Search Tree (Medium · LeetCode #98)

Problem statement. Determine whether a binary tree is a valid BST: left subtree keys strictly less than the node, right subtree keys strictly greater, and both subtrees are valid BSTs.

• Example: [2,1,3] -> true.
• Example: [5,1,4,null,null,3,6] -> false (right child 4 has left child 3 which is less than 5).
• Constraints: nodes in [1, 10^4], -2^31 <= val <= 2^31 - 1.

How the interviewer asks / follow-ups.

• Fintech disguise: "A sorted index of transaction IDs/timestamps is stored as a BST. Verify the index is not corrupted after a bad deploy/migration." Or "validate a range-partitioned routing tree".
• Follow-ups: iterative inorder with a stack; Morris traversal for O(1) space; what if duplicates are allowed (on the left only? then use <=/> accordingly, ask the interviewer); how to handle Integer.MIN_VALUE/MAX_VALUE nodes; recover a BST with two swapped nodes (#99).
• Evaluating: knowing the BST property is about ALL descendants, not only immediate children; correct bounds; the integer-limit trap.

Approach 1: Brute force (wrong): compare only with immediate children. Fails on [5,4,6,null,null,3,7] since 3 < 5 sits in the right subtree. Mention it as the classic mistake.

Approach 1b: Brute force (correct). For each node, check that max of left subtree < node < min of right subtree via separate traversals. Time O(n^2) worst case (skewed), Space O(h).

Approach 2: Recursion with bounds (optimal). Intuition: each node must lie in an open interval (lo, hi) inherited from ancestors. Going left tightens hi to the parent value; going right tightens lo. Trace [5,1,4,null,null,3,6]: 5 in (-inf,+inf); 1 in (-inf,5) ok; 4 in (5,+inf)? 4 is not > 5 -> false. Use Integer objects as null for "no bound" (or long), so Integer.MIN_VALUE and MAX_VALUE nodes are valid.

Approach 3: Inorder traversal. A BST's inorder is strictly increasing. Keep prev and fail if cur <= prev. Iterative form works with an explicit stack (no recursion depth problem). Morris traversal makes extra space O(1).

Java code.

// Approach 2: bounds recursion. Integer (nullable) bounds avoid the MIN_VALUE/MAX_VALUE trap.
static boolean isValidBST(TreeNode root) {
    return valid(root, null, null);
}
private static boolean valid(TreeNode n, Integer lo, Integer hi) {
    if (n == null) return true;
    if ((lo != null && n.val <= lo) || (hi != null && n.val >= hi)) return false; // strict
    return valid(n.left, lo, n.val) && valid(n.right, n.val, hi);
}

// Approach 3: iterative inorder, strictly increasing check
static boolean isValidBSTIter(TreeNode root) {
    Deque<TreeNode> stack = new ArrayDeque<>();
    TreeNode cur = root;
    Integer prev = null;
    while (cur != null || !stack.isEmpty()) {
        while (cur != null) { stack.push(cur); cur = cur.left; }
        cur = stack.pop();
        if (prev != null && cur.val <= prev) return false;
        prev = cur.val;
        cur = cur.right;
    }
    return true;
}

Complexity.

• Correct brute force: Time O(n^2) worst case, Space O(h).
• Bounds recursion: Time O(n), every node checked once. Space O(h) stack.
• Iterative inorder: Time O(n), Space O(h) explicit stack (Morris variant: O(1)).

Edge cases / pitfalls. Initializing bounds with Integer.MIN_VALUE/MAX_VALUE wrongly rejects a node equal to those values (e.g. a single node Integer.MIN_VALUE); use null/Long. Strictness: [2,2,2] is NOT valid. Comparing only parent-child is wrong. Single node and null are valid. In the inorder version, prev as int initialized to MIN_VALUE has the same trap.

Pattern & related. BST property via bounds or inorder monotonicity. Related: Recover Binary Search Tree (#99), Kth Smallest in BST (#230), Convert Sorted Array to BST (#108), Minimum Distance Between BST Nodes (#783).

10. Kth Smallest Element in a BST (Medium · LeetCode #230)

Problem statement. Given the root of a BST and an integer k (1-indexed), return the k-th smallest value.

• Example: root=[3,1,4,null,2], k=1 -> 1.
• Example: root=[5,3,6,2,4,null,null,1], k=3 -> 3.
• Constraints: 1 <= k <= n <= 10^4, 0 <= val <= 10^4.

How the interviewer asks / follow-ups.

• Fintech disguise: "Given a BST of transaction amounts, find the k-th smallest (or 'k-th largest' for top-spenders; or a percentile)." Or "k-th earliest timestamped event".
• Follow-ups: what if the BST is modified often (insert/delete) and you must answer many k-th queries? (Augment each node with the size of its left subtree/subtree count for O(h) queries; or use an order-statistic tree; or a balanced tree like TreeMap with augmentation.) Morris traversal for O(1) space. Recursion depth on skewed tree. k-th largest (reverse inorder).
• Evaluating: inorder = sorted order, early exit, and the augmentation idea for the follow-up.

Approach 1: Brute force. Traverse all nodes into a list, sort, return index k-1. Time O(n log n), Space O(n).

Approach 2: Full inorder into a list. Inorder gives sorted output: Time O(n), Space O(n). Return list.get(k-1).

Approach 3: Iterative inorder with early stop (optimal for one query). Intuition: stop after popping the k-th node. Time O(h + k). Trace [5,3,6,2,4,null,null,1], k=3: push 5,3,2,1; pop 1 (k=2 left), go right (null), pop 2 (k=1), pop 3 (k=0) -> return 3.

Approach 4: Augmented BST (for frequent updates/queries). Store leftCount in each node: if k <= leftCount go left; if k == leftCount+1 return node; else go right with k - leftCount - 1. Query O(h), update O(h) to maintain counts.

Java code.

static int kthSmallest(TreeNode root, int k) {
    Deque<TreeNode> stack = new ArrayDeque<>();
    TreeNode cur = root;
    while (cur != null || !stack.isEmpty()) {
        while (cur != null) {                         // go as far left as possible
            stack.push(cur);
            cur = cur.left;
        }
        cur = stack.pop();                            // next smallest
        if (--k == 0) return cur.val;                 // early exit
        cur = cur.right;
    }
    throw new IllegalArgumentException("k out of range");
}

Complexity.

• Sort-all: Time O(n log n), Space O(n).
• Inorder list: Time O(n), Space O(n).
• Iterative with early exit: Time O(h + k), Space O(h) for the stack (O(n) skewed). Morris variant: O(1) space, time O(n) worst case.
• Augmented tree: Query O(h), Space O(n) extra for counts.

Edge cases / pitfalls. Validate k range (throw or return sentinel). Duplicates are not present per constraints; with duplicates clarify semantics. Do not decrement k before checking if you use a different order of operations. For the k-th largest, traverse right first (reverse inorder).

Pattern & related. Inorder of BST = sorted sequence; order-statistic augmentation. Related: Validate BST (#98), BST Iterator (#173), Kth Largest Element in an Array (#215), Find Median from Data Stream (#295).

11. Lowest Common Ancestor of a BST (Medium · LeetCode #235)

Problem statement. Given a BST and two nodes p and q that exist in it, find their lowest common ancestor (the deepest node that has both as descendants; a node counts as a descendant of itself).

• Example: root=[6,2,8,0,4,7,9,null,null,3,5], p=2, q=8 -> 6.
• Example: same tree, p=2, q=4 -> 2 (a node can be its own ancestor).
• Constraints: nodes in [2, 10^5], unique values, p != q, both exist.

How the interviewer asks / follow-ups.

• Fintech disguise: "Given a sorted hierarchy (e.g. account-number ranges or IP/BIN ranges in a BST), find the smallest enclosing range node covering two entries / the nearest common parent account."
• Follow-ups: do it iteratively with O(1) space; what if it is a general binary tree (#236: need post-order, no BST property)? What if p or q may be missing? What if parent pointers exist (#1650)? Multiple queries (Euler tour + RMQ / binary lifting).
• Evaluating: exploiting the BST ordering instead of applying the general-tree solution.

Approach 1: Brute force. Find the root-to-node path for p and for q (list of ancestors), then walk both paths and return the last common node. Time O(n) (O(h) in a BST using search), Space O(h).

Approach 2: BST descent (optimal). Intuition: the LCA is the first node whose value lies between p and q (inclusive) as you descend from the root. If both values are smaller, LCA is in the left subtree; if both are larger, go right; otherwise the paths diverge here, so this node is the LCA. Trace p=2,q=4 in the example: root 6: both < 6 -> go left to 2; 2 is not > both or < both (p equals 2) -> return 2.

Java code.

static TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    TreeNode cur = root;
    while (cur != null) {
        if (p.val < cur.val && q.val < cur.val) cur = cur.left;       // both in left
        else if (p.val > cur.val && q.val > cur.val) cur = cur.right; // both in right
        else return cur;                                              // split point (or equals p/q)
    }
    return null;                                                      // unreachable if p, q are in the tree
}

Complexity.

• Path-based brute force: Time O(h) via BST search per node (O(n) for a general tree), Space O(h).
• BST descent: Time O(h) (O(log n) balanced, O(n) skewed). Space O(1) iterative (a recursive version uses O(h) stack).

Edge cases / pitfalls. If p is an ancestor of q, the answer is p. Use inclusive handling (equality falls into the else). Don't use p.val - q.val style arithmetic (overflow). Works only if both nodes exist; if not guaranteed, verify with a search first. Don't confuse with the general-tree LCA (#236).

Pattern & related. BST navigation using ordering (binary-search-like). Related: LCA of a Binary Tree (#236), LCA of Deepest Leaves (#1123), Search in a BST (#700), Closest BST Value (#270).

12. Implement Trie (Prefix Tree) (Medium · LeetCode #208)

Problem statement. Implement a Trie with insert(word), search(word) (exact match) and startsWith(prefix).

• Example: insert("apple"), search("apple") -> true, search("app") -> false, startsWith("app") -> true, insert("app"), search("app") -> true.
• Constraints: length 1..2000, lowercase letters, up to 3*10^4 calls.

How the interviewer asks / follow-ups.

• Fintech disguise: "BIN/IIN prefix lookup for card numbers: given the first 6-8 digits find the issuing network/bank; longest-prefix match to route a card to Visa/Mastercard/RuPay." Also "autocomplete for merchant names / UPI VPA handles", "blocklist of account number prefixes", "IFSC prefix routing".
• Follow-ups: use HashMap children vs children[26] (memory vs speed; for digits use [10]); longest-prefix match; return all words with a prefix (autocomplete, top-k by frequency); delete a word; memory optimization (compressed/radix trie); thread-safety for concurrent reads/updates (copy-on-write or read-write lock); compare with a HashSet (prefix queries are O(L) in a trie, O(n*L) in a set) or a sorted array + binary search.
• Evaluating: node design, the isEnd flag (why "app" is not found just because "apple" is), and complexity in terms of word length, not number of words.

Approach 1: Brute force. Keep a HashSet<String> for search; for startsWith scan all words with startsWith. insert/search O(L), startsWith O(N*L) where N = words stored. Space O(total chars).

Approach 2: Trie (optimal). Intuition: each edge is a character; words that share a prefix share a path. search needs the final node to be marked as the end of a word; startsWith only needs the path to exist. Trace: insert "apple": a-p-p-l-e, mark e as end. search("app") walks a-p-p, reaches a node with end=false -> false; startsWith("app") -> path exists -> true. After insert("app") the 2nd p node gets end=true.

Java code.

class Trie {
    private static class Node {
        Node[] next = new Node[26];                   // use Node[10] for digit-only card BINs
        boolean end;                                   // a word ends exactly here
    }
    private final Node root = new Node();

    public void insert(String word) {
        Node n = root;
        for (char ch : word.toCharArray()) {
            int i = ch - 'a';
            if (n.next[i] == null) n.next[i] = new Node();
            n = n.next[i];
        }
        n.end = true;
    }

    public boolean search(String word) {
        Node n = find(word);
        return n != null && n.end;                    // path must exist AND be a complete word
    }

    public boolean startsWith(String prefix) {
        return find(prefix) != null;
    }

    private Node find(String s) {                     // node reached by s, or null
        Node n = root;
        for (char ch : s.toCharArray()) {
            n = n.next[ch - 'a'];
            if (n == null) return null;
        }
        return n;
    }
}

Complexity.

• HashSet approach: insert/search O(L), startsWith O(N*L); Space O(sum of lengths).
• Trie: insert/search/startsWith O(L), L = length of the string, independent of how many words are stored. Space O(total characters * alphabet size) worst case for array children (26 * nodes references); a HashMap child map uses space proportional to actual edges.
• No recursion, so no stack concerns.

Edge cases / pitfalls. Forgetting end makes search("app") wrongly true. Characters outside a-z break ch - 'a' (use a map or validate; card numbers need digits only). Inserting an existing word or a prefix of an existing word is fine. Empty string: search("") is false unless inserted (the root's end). Memory: 26 pointers per node is heavy for sparse data; mention a map or compressed trie.

Pattern & related. Prefix tree for string-set queries. Related: Design Add and Search Words (#211), Word Search II (#212), Longest Common Prefix (#14), Replace Words (#648), Design Search Autocomplete System (#642), Map Sum Pairs (#677).

13. Design Add and Search Words Data Structure (Medium · LeetCode #211)

Problem statement. Design WordDictionary with addWord(word) and search(word), where search may contain '.' matching any single letter.

• Example: add "bad","dad","mad"; search("pad") -> false; search("bad") -> true; search(".ad") -> true; search("b..") -> true.
• Constraints: word length 1..25; addWord words are lowercase letters; search has lowercase letters or . (at most 2 dots in the LeetCode constraints); up to 10^4 calls.

How the interviewer asks / follow-ups.

• Fintech disguise: "Match masked card patterns / account-number templates such as 4111-****", "search blocked-merchant patterns with wildcards", "IFSC / VPA wildcard search".
• Follow-ups: what if * can match a sequence (becomes DP/memoized recursion)? What about thousands of dots (worst-case blow-up; mitigate with length-bucketed hash sets)? Iterative DFS to avoid recursion; thread safety; memory.
• Evaluating: extending a trie with branching DFS on wildcards, correct termination and end check.

Approach 1: Brute force. Store words in a list (or in buckets by length); for each search compare character by character against every candidate of the same length. Time O(NL) per search, Space O(NL).

Approach 2: Trie + DFS on wildcards (optimal). Intuition: for a normal letter follow the single child; for . try every non-null child and succeed if any branch succeeds. Trace search("b..") after adding bad/dad/mad: root -> 'b'; '.' tries child 'a' -> '.' tries child 'd' -> index reaches end, node d has end=true -> true.

Java code.

class WordDictionary {
    private static class Node {
        Node[] next = new Node[26];
        boolean end;
    }
    private final Node root = new Node();

    public void addWord(String word) {
        Node n = root;
        for (char ch : word.toCharArray()) {
            int i = ch - 'a';
            if (n.next[i] == null) n.next[i] = new Node();
            n = n.next[i];
        }
        n.end = true;
    }

    public boolean search(String word) {
        return dfs(word, 0, root);
    }

    private boolean dfs(String w, int i, Node n) {
        if (n == null) return false;
        if (i == w.length()) return n.end;            // consumed all chars: must be a word end
        char ch = w.charAt(i);
        if (ch != '.') return dfs(w, i + 1, n.next[ch - 'a']);
        for (Node child : n.next)                     // wildcard: try every branch
            if (child != null && dfs(w, i + 1, child)) return true;
        return false;
    }
}

Complexity.

• Brute force: addWord O(L), search O(NL), Space O(NL).
• Trie: addWord O(L). search O(L) with no dots; with d dots worst case O(26^d * L) in general (bounded by the number of trie nodes, so O(total nodes) at worst). Space O(total chars) nodes. Recursion stack O(L).

Edge cases / pitfalls. Pattern longer than any word ("....") -> false because paths run out. A pattern that is a strict prefix of a stored word (e.g. "ba" vs "bad") must be false: check end at the final index. Pattern "." on an empty dictionary returns false. Empty pattern: returns root.end, false.

Pattern & related. Trie plus backtracking on branching characters. Related: Implement Trie (#208), Word Search II (#212), Wildcard Matching (#44), Regular Expression Matching (#10).

14. Word Search II (Hard · LeetCode #212)

Problem statement. Given an m x n board of lowercase letters and a list of words, return all words that can be formed by sequentially adjacent (horizontal/vertical) cells, using each cell at most once per word.

• Example: board [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]], words ["oath","pea","eat","rain"] -> ["eat","oath"].
• Example: board [["a","b"],["c","d"]], words ["abcb"] -> [].
• Constraints: 1 <= m, n <= 12, 1 <= words.length <= 3*10^4, word length 1..10, all words unique.

How the interviewer asks / follow-ups.

• Fintech disguise: "Scan a grid of OCR'd characters / a keypad grid for any blacklisted keywords" or "find all dictionary words in a character matrix" (a word-game / fraud keyword scan).
• Follow-ups: why not run Word Search I (#79) for each word (too slow); how pruning of the trie improves the worst case; avoiding duplicate results; larger boards or dictionaries (memory of trie); iterative DFS.
• Evaluating: combining trie and backtracking, in-place visited marking with restoration, dedup, and pruning.

Approach 1: Brute force. For each word, run Word Search I: DFS from every cell. Time O(W * m*n * 3^(L-1)) where W = number of words and L = max word length (4 directions for the first step, then at most 3 because you do not go back). Space O(L) recursion.

Approach 2: Trie + single backtracking pass (optimal). Intuition: build a trie of all words once. DFS from each cell while walking the trie in lockstep; if the current letter has no child in the trie, abandon this path immediately (this shares work across all words with common prefixes). When reaching a node that stores a complete word, record it and clear it (dedup). Optionally prune trie leaves after use so exhausted branches are not explored again. Trace on the example: start at (0,0) 'o' -> trie child 'o' exists -> neighbor 'a' (0,1) -> 'a' child exists -> 't' (1,1) -> 'h' (2,1) -> node 'h' stores "oath" -> add. The word "pea" never matches because trie root has child 'p' but no board cell 'p'; "rain" fails after 'r'-'a'-'i' paths not adjacent.

Java code.

class Solution {
    private static class TrieNode {
        TrieNode[] next = new TrieNode[26];
        String word;                                  // non-null if a word ends here
    }

    public List<String> findWords(char[][] board, String[] words) {
        TrieNode root = new TrieNode();
        for (String w : words) {
            TrieNode n = root;
            for (char ch : w.toCharArray()) {
                int i = ch - 'a';
                if (n.next[i] == null) n.next[i] = new TrieNode();
                n = n.next[i];
            }
            n.word = w;
        }
        List<String> res = new ArrayList<>();
        for (int i = 0; i < board.length; i++)
            for (int j = 0; j < board[0].length; j++)
                dfs(board, i, j, root, res);
        return res;
    }

    private void dfs(char[][] b, int i, int j, TrieNode parent, List<String> res) {
        if (i < 0 || j < 0 || i >= b.length || j >= b[0].length) return;
        char ch = b[i][j];
        if (ch == '#') return;                        // already used on this path
        TrieNode node = parent.next[ch - 'a'];
        if (node == null) return;                     // no word has this prefix: prune

        if (node.word != null) {                      // found a word
            res.add(node.word);
            node.word = null;                         // avoid duplicates
        }
        b[i][j] = '#';                                // mark visited
        dfs(b, i + 1, j, node, res);
        dfs(b, i - 1, j, node, res);
        dfs(b, i, j + 1, node, res);
        dfs(b, i, j - 1, node, res);
        b[i][j] = ch;                                 // backtrack (restore)

        // Prune: remove exhausted leaf so later searches skip this branch
        boolean leaf = node.word == null;
        for (TrieNode c : node.next) if (c != null) { leaf = false; break; }
        if (leaf) parent.next[ch - 'a'] = null;
    }
}

Complexity.

• Brute force: Time O(W * m*n * 3^(L-1)), Space O(L).
• Trie + backtracking: Time O(m*n * 3^(L-1)) worst case, independent of W in the DFS (building the trie costs O(total characters of all words)); in practice much faster thanks to prefix pruning. Space O(total characters) for the trie plus O(L) recursion stack.

Edge cases / pitfalls. Restore the cell after DFS (backtracking). Use a sentinel that cannot be a letter ('#'). Prevent duplicate answers (a word can be found via several paths): null out node.word. A word that is a prefix of another (e.g. "a" and "aa" on [a][a]) still works because the word is recorded when passing the node. A word longer than the number of cells or needing a cell twice is never matched (["aaa"] on [a,a] -> empty). Mutating the board is acceptable in the interview; mention you restore it (not thread-safe on a shared board). The result order is unspecified; sort if the tests need it.

Pattern & related. Trie + backtracking (DFS with undo) on a grid. Related: Word Search (#79), Implement Trie (#208), Design Add and Search Words (#211), Boggle Game, Concatenated Words (#472).