Binary tree traversals

Recognize it from

Print nodes left-to-right as in a BST. Walk a tree “level by level”. Zigzag / spiral level order. “Return values grouped by depth.” Anything that needs children of the whole current layer before the next layer.

What it actually does

Inorder is a recursive DFS: the call stack holds the path from the root down to the node you are about to visit. You fully finish the left subtree, visit the node, then fully finish the right subtree. There is no explicit Deque — Java’s stack frames are the stack. On a BST that visit order is sorted.

Level-order is BFS. You put the root in a queue. Each loop iteration peels off the current layer (q.size() at the start of the layer) and offers that node’s children. Trees have no cycles, so you do not need a visited set; a child is offered exactly once, from its parent. Mark-on-enqueue here just means “offer as soon as you see the child,” the same habit as graph BFS.

List<Integer> inorder(TreeNode root) {
    List<Integer> out = new ArrayList<>();
    walk(root, out);
    return out;
}

void walk(TreeNode n, List<Integer> out) {
    if (n == null) return;                    // empty child: this frame is done
    walk(n.left, out);                        // whole left subtree sits deeper on the call stack
    out.add(n.val);                           // visit only after left has returned
    walk(n.right, out);                       // right runs after this value is recorded
}

List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> out = new ArrayList<>();
    if (root == null) return out;             // empty tree: zero levels, not one empty level
    Deque<TreeNode> q = new ArrayDeque<>();
    q.offer(root);                            // enqueue as soon as discovered; tree cannot re-visit
    while (!q.isEmpty()) {
        int sz = q.size();                    // freeze layer width; later offers belong to the next layer
        List<Integer> level = new ArrayList<>();
        for (int i = 0; i < sz; i++) {
            TreeNode n = q.poll();
            level.add(n.val);
            if (n.left != null) q.offer(n.left);
            if (n.right != null) q.offer(n.right);
        }
        out.add(level);
    }
    return out;
}

Example 1 — simple

Three nodes. Inorder should read like a sorted BST. Level-order should print the root alone, then both children.

Inorder answer: 1, 2, 3. Level-order: queue starts [2] → layer [2] then offers 1 and 3 → layer [1, 3]. Answer: [[2], [1, 3]].

Example 2 — every step

Seven nodes. Every recursive call and every queue poll is in the tables. No skipped visits.

Inorder answer: 4, 2, 5, 1, 6, 3, 7.

Level-order answer: [[1], [2, 3], [4, 5, 6, 7]].

BST search and insert

Recognize it from

“Left subtree < node < right subtree.” Search, insert, or validate a binary search tree. “Floor / ceil in a BST.” Convert sorted list / array into a BST. Anything that should be a compare-and-walk, not a full scan.

What it actually does

At each node you compare the key with n.val. Strictly smaller → go left. Strictly larger → go right. Equal → found. If you walk off a null child, the key is absent. Insert is the same walk; the null you would have fallen off becomes a new node, wired onto the parent that just compared.

Use Integer.compare so you never write v - n.val (that overflows). Duplicates: pick a policy and keep it — this page ignores equals on insert (no new node). Search still returns the first equal node.

TreeNode search(TreeNode n, int key) {
    if (n == null) return null;               // walked off a leaf: key is not here
    if (key == n.val) return n;
    if (key < n.val) return search(n.left, key);
    return search(n.right, key);
}

TreeNode search(TreeNode n, int key) {
    while (n != null) {
        int c = Integer.compare(key, n.val);  // never key - n.val
        if (c == 0) return n;
        n = (c < 0) ? n.left : n.right;
    }
    return null;
}

TreeNode insert(TreeNode n, int key) {
    if (n == null) return new TreeNode(key);  // this null slot is the insertion point
    int c = Integer.compare(key, n.val);
    if (c < 0) n.left = insert(n.left, key);
    else if (c > 0) n.right = insert(n.right, key);
    // c == 0: keep the existing node (duplicate policy)
    return n;                                 // parent rebinds the child pointer
}

Example 1 — simple

Search 4 in a 5-node BST.

Answer: the node whose value is 4.

Example 2 — every step

Failed search that goes left, then right, then right. Key = 8.

Answer: not found. Insert of 8 would create a new node as 7.right — that is the same walk, replacing the final null with a node.

Tree DP — max path that can bend

Recognize it from

“Maximum path sum” where a path may start and end at any nodes (not only root-to-leaf). “Path that bends through a node.” Diameter (longest path, counting edges or nodes). “Gain you can still hand to your parent” vs “best path seen anywhere.”

What it actually does

Each node computes two different numbers. The return value is the best chain that still has a free end at this node, so the parent can extend it: n.val + max(leftGain, rightGain). The global best may bend: leftGain + node + rightGain, using both children. That bent path cannot be returned upward — the parent would fork.

A negative child cannot help any path that includes it, so both versions clamp that child gain to 0 (drop the child). That is the any-node variant. Leaf-to-leaf is a different spec: you must not clamp, because a leaf path cannot drop a child. This card is the any-node / bend version, matching the Live Code shape in the notebook’s related card.

int best = Integer.MIN_VALUE;

int maxPathSum(TreeNode root) {
    best = Integer.MIN_VALUE;
    gain(root);
    return best;
}

int gain(TreeNode n) {
    if (n == null) return 0;
    int L = gain(n.left);
    int R = gain(n.right);
    if (L < 0) L = 0;                         // negative child cannot improve a path
    if (R < 0) R = 0;
    int bend = L + n.val + R;                 // path that uses both sides, ends here
    if (bend > best) best = bend;             // record even if we do not return the bend
    return n.val + Math.max(L, R);            // parent may extend only one side
}

class MaxPathAnyNode {
    private int best = Integer.MIN_VALUE;

    public int maxPathSum(TreeNode root) {
        best = Integer.MIN_VALUE;
        gain(root);
        return best;
    }

    private int gain(TreeNode n) {
        if (n == null) return 0;
        int L = Math.max(0, gain(n.left));    // may drop a negative branch
        int R = Math.max(0, gain(n.right));
        best = Math.max(best, L + n.val + R);
        return n.val + Math.max(L, R);
    }
}

Example 1 — simple

Three nodes, all positive. The bend through the root is the whole tree.

Answer: 6 (path 2–1–3). The value returned from the root (4) is not the answer; best is.

Example 2 — every step

The best path does not go through the root. Watch best jump to 42 at node 20, then refuse to be beaten by the root’s bend.

Answer: 42, path 15–20–7. Root’s own bend is 34. Returning 25 from the root would be wrong if you treated the return value as the answer.

Lowest common ancestor

Recognize it from

“Lowest common ancestor of p and q.” Distance between two nodes (path = depth(p)+depth(q)−2·depth(lca)). Kth ancestor. “First node that sits on both paths to the root.”

What it actually does

Simple version: BFS (or DFS) to record each node’s parent, walk from p to the root collecting a set, then walk from q until you hit that set. The first hit is the LCA. That uses extra maps.

Interview version: one DFS. If the current node is null, p, or q, return it. Recurse left and right. If both sides return non-null, p and q split here — this node is the LCA. If only one side is non-null, bubble that answer up (the other subtree did not contain either node). Null returns mean “neither p nor q lives under me.” Both nodes are assumed present.

TreeNode lca(TreeNode root, TreeNode p, TreeNode q) {
    Map<TreeNode, TreeNode> par = new HashMap<>();
    Deque<TreeNode> dq = new ArrayDeque<>();
    par.put(root, null);
    dq.offer(root);                           // parent-map BFS; offer once from parent
    while (!par.containsKey(p) || !par.containsKey(q)) {
        TreeNode n = dq.poll();
        if (n.left != null) {
            par.put(n.left, n);
            dq.offer(n.left);
        }
        if (n.right != null) {
            par.put(n.right, n);
            dq.offer(n.right);
        }
    }
    Set<TreeNode> seen = new HashSet<>();
    while (p != null) { seen.add(p); p = par.get(p); }
    while (!seen.contains(q)) q = par.get(q);
    return q;
}

TreeNode lca(TreeNode n, TreeNode p, TreeNode q) {
    if (n == null || n == p || n == q) return n;
    TreeNode L = lca(n.left, p, q);
    TreeNode R = lca(n.right, p, q);
    if (L != null && R != null) return n;     // p and q came from different sides
    return (L != null) ? L : R;               // bubble the non-null side, or null
}

Example 1 — simple

p and q are siblings. LCA is their parent.

Answer: node 3.

Example 2 — every step

p in the left subtree, q in the right. Null returns bubble up through a node that contains neither.

Answer: node 6. The interesting null is lca(4): that whole subtree reports “not here,” so 2 bubbles p upward until 6 sees q from the other side.

Size-k min-heap — kth largest

Recognize it from

“Kth largest in a stream.” Top-k frequent. Merge k sorted lists (heap of heads). Connect ropes / combine garlands. Median of a stream (two heaps). “Keep only k candidates.”

What it actually does

A min-heap of size k stores the k largest values seen so far, with the smallest of those k on top. That top is the current kth largest. When a new value arrives, offer it; if size exceeds k, poll — you throw away the smallest, which cannot be among the k largest anymore.

Java’s PriorityQueue is a min-heap by default. For kth smallest you would invert to a max-heap of size k. Merge-k and ropes are the same DS: always pull the current minimum in O(log k) or O(log n).

int kthLargest(int[] a, int k) {
    Arrays.sort(a);                           // idea: order everything, pick from the right
    return a[a.length - k];                   // k=1 → last element = largest
}

class KthLargest {
    private final int k;
    private final PriorityQueue<Integer> min;

    KthLargest(int k, int[] nums) {
        this.k = k;
        min = new PriorityQueue<>();          // min-heap; peek = smallest of the k largest
        for (int x : nums) add(x);
    }

    int add(int val) {
        min.offer(val);
        if (min.size() > k) min.poll();       // drop the value that can no longer be kth
        return min.peek();                    // stream query: kth among all adds so far
    }
}

Example 1 — simple

Stream of four numbers, k = 2. Heap shown with the minimum on the left.

Answer after the stream: 4 (the two largest are 7 and 4). After only two numbers the peek is 1 — that is honest: with two values the 2nd largest is the min of them.

Example 2 — every step

Every offer and poll for [3, 2, 1, 5, 6, 4], k = 2.

Answer: 5 (largest = 6, 2nd = 5). Sorted unique view: 1,2,3,4,5,6 — index n−k agrees with the heap peek.

Trie insert and search

Recognize it from

Autocomplete. “Does this word exist, vs is it only a prefix.” Word dictionary with add/search. Replace words with a shortest root. Search-suggestions as you type. Anything that shares string prefixes.

What it actually does

A trie is a tree whose edges are characters. Insert walks the word, creating a child node when the letter is missing, then marks end = true on the last node. Search walks the same letters and succeeds only if every hop exists and that last node is an end. If you land on a node with end = false, you found a prefix of some inserted word, not the word itself.

Simple version stores children in a HashMap (any character). Interview version uses Node[26] for lowercase a–z and a shared walk helper so search and startsWith differ by one boolean.

class Trie {
    Map<Character, Trie> kids = new HashMap<>();
    boolean end;

    void insert(String w) {
        Trie n = this;
        for (int i = 0; i < w.length(); i++) {
            char c = w.charAt(i);
            n.kids.putIfAbsent(c, new Trie()); // create the hop if this prefix is new
            n = n.kids.get(c);
        }
        n.end = true;                          // word ends here; prefixes stay end=false
    }

    boolean search(String w) {
        Trie n = this;
        for (int i = 0; i < w.length(); i++) {
            n = n.kids.get(w.charAt(i));
            if (n == null) return false;       // missing letter: not in the trie
        }
        return n.end;
    }
}

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

    void insert(String w) {
        Node n = root;
        for (int i = 0; i < w.length(); i++) {
            int x = w.charAt(i) - 'a';
            if (n.ch[x] == null) n.ch[x] = new Node();
            n = n.ch[x];
        }
        n.end = true;
    }

    boolean search(String w) {
        Node n = walk(w);
        return n != null && n.end;            // must be a marked word, not only a prefix
    }

    boolean startsWith(String p) {
        return walk(p) != null;               // landing on any node is enough
    }

    private Node walk(String s) {
        Node n = root;
        for (int i = 0; i < s.length(); i++) {
            int x = s.charAt(i) - 'a';
            if (n.ch[x] == null) return null;
            n = n.ch[x];
        }
        return n;
    }
}

Example 1 — simple

Insert "a" then "app".

After both inserts, search("a") is true and search("ap") is false: the middle p is only a prefix.

Example 2 — every step

Insert "app", "apple", "apt". Then search "ap", "app", "apex" — every node hop.

Answers: search("ap") = false, search("app") = true, search("apex") = false. The first is the prefix trap; the third is a missing hop.