Binary Tree, BST & Divide and Conquer

Trees are where interviews start rewarding a specific way of thinking rather than a specific trick. Almost every tree problem in this session is four lines of recursion — the difficulty is not the code, it is seeing the problem as "solve the two subtrees, then combine." This session builds that muscle from the ground up: the vocabulary (binary tree vs BST vs balanced vs complete), the three traversals and their iterative stack templates, the recursion-versus-divide-and-conquer distinction that turns an O(n log n) solution into O(n), and the BST invariant that trips up more candidates than any other single idea.

The Vocabulary You Have to Get Right

Before any code, the session pins down four definitions, because interviewers use them as filters — mix them up and the rest of the answer is suspect.

• Binary tree — every node has at most two children and there are no cycles. That "no cycle, connected" phrasing is also how you explain the difference from a graph: a tree is a special connected acyclic graph.
• Binary search tree (BST) — for every node, all values in the left subtree are less than the node's value, and all values in the right subtree are greater. The invariant is over the whole subtree, not just the two children — remember this exact wording.
• Complete / full binary tree (the heap shape) — a complete tree fills every level except possibly the last, and the last level is packed as far left as possible (this is what lets a heap live in an array). A full (or proper) tree is stricter: every non-leaf has exactly two children.
• Balanced binary tree — for every node, the heights of its left and right subtrees differ by at most 1. This is the property LC 110 asks you to verify.

Depth and height both count "number of levels" — the session treats them interchangeably for these problems, which is fine as long as you are consistent (a null child contributes 0). Now the node itself. The mental model that makes trees click is that a tree is a linked list with two next pointers. The same discipline carries over: never lose the root reference, always null-check before you dereference, and treat null as the all-important termination condition.

The node itself is the obvious three fields — an int val plus left and right references — with a few optional levers the notes flag: add a parent pointer when you need to walk upward, switch to a List<TreeNode> children for an N-ary tree, and when the fan-out is fixed and small — the 26 letters of a Trie — use a plain TreeNode[26] array instead of a map for speed.

The Three Traversals

Every traversal visits the root, the left subtree, and the right subtree — the name just says when the root is visited relative to its subtrees:

• Preorder (root → left → right): 15 5 3 6 20 17 23
• Inorder (left → root → right): 3 5 6 15 17 20 23 — ascending, because the tree is a BST
• Postorder (left → right → root): 3 6 5 17 23 20 15

Those numbers come from the running example tree — root 15, children 5 and 20, leaves 3, 6, 17, 23. The recursive versions (LC 144, LC 94, LC 145) are identical except for where the visit line sits: move that one line and you change the order. That is the whole trick.

void preorder(TreeNode root) {
    if (root == null) return;       // termination: the null child
    visit(root.val);                // ← here      → preorder
    preorder(root.left);
    // visit(root.val);             // ← here      → inorder (ascending for a BST)
    preorder(root.right);
    // visit(root.val);             // ← here      → postorder
}

The inorder position is worth internalizing: because it emits a BST in sorted order, "is this a valid BST?" becomes "is the inorder sequence increasing?" To check that on the fly you keep a global prev pointer — a local variable resets on every recursive call, so the previous node has to live outside the recursion. That global-prev pattern reappears in half the BST problems below; it is worth its own line of muscle memory.

Iterative Traversal: One Stack Template

Interviewers love "now do it without recursion" because it tests whether you understand that recursion is just an explicit stack. There is one template that handles all three orders with a single control structure — you only change when you record the value.

public List<Integer> inorder(TreeNode root) {
    List<Integer> ans = new ArrayList<>();
    Deque<TreeNode> st = new ArrayDeque<>();
    while (root != null || !st.isEmpty()) {
        if (root == null) {          // left spine exhausted → pop and go right
            root = st.pop();
            ans.add(root.val);        // inorder: record on the way back up
            root = root.right;
        } else {                     // keep pushing the left spine
            st.push(root);
            root = root.left;
        }
    }
    return ans;
}

The variations fall out of that one skeleton. For preorder, record the value on the way down (in the else branch, right before root = root.left). For postorder, there is a slick shortcut: postorder is a "root → right → left" preorder, reversed. Build the list by pushing right before left, then call Collections.reverse(ans) (or prepend with addFirst). If you would rather not think that hard, the simplest iterative preorder is even shorter: push root, then loop — pop, record, and push right first so left comes off the stack first.

Recursion vs Divide and Conquer

This is the conceptual spine of the session. Both approaches recurse, but they think differently. Plain recursion threads a running result through the call (often via a global). Divide and conquer instead asks each subtree to return its own answer, and combines those two answers at the current node — the shape of a postorder traversal. Depth is the cleanest first example: a node's height is 1 + max(left height, right height), and you cannot know it until both children report back.

// clean: fine when nothing happens at the node
public int getDepth(TreeNode root) {
    if (root == null) return 0;
    return 1 + Math.max(getDepth(root.left), getDepth(root.right));
}

// expanded: prefer this — the "wall" gives you a place to process or short-circuit
public int getDepth(TreeNode root) {
    if (root == null) return 0;
    int left  = getDepth(root.left);
    int right = getDepth(root.right);   // ── the wall: both subtrees have reported ──
    return 1 + Math.max(left, right);   // combine here; add logic above this line
}

The one-liner is tempting, but the notes are emphatic: keep the two recursive calls on their own lines with a "wall" between them and the combine step. The moment a problem needs to inspect the two subtree results — compare them, short-circuit, accumulate a global maximum — you already have the seam to do it. Every recursion here is O(n): one call per node, each node visited once.

The iterative retellings are worth knowing but rarely worth writing. DFS with an explicit stack carries a parallel stack of depths (push the node and its depth together, track the running max). BFS with a queue is the natural fit for depth: process the queue one full level at a time — grab size = queue.size(), drain exactly that many nodes while enqueuing their children, then increment a level counter. That level-by-level BFS is the skeleton behind an entire family of problems and returns in force in Session 8.

LC 111 Minimum Depth — the null-child trap

Reusing the max-depth recursion with Math.min is wrong, and the bug is subtle. When a node has only one child, the missing side returns 0, and min(0, something) collapses to 0 — which would report a depth that ignores the only real path. The fix is to treat a null child as "not a real branch" — if one side is 0, follow the other; only take the true min when both children exist: return (left == 0 || right == 0) ? left + right + 1 : Math.min(left, right) + 1;

Balanced Tree (LC 110): O(n log n) → O(n)

The direct translation of the definition is correct but slow: at each node compute both subtree heights, check the difference is ≤ 1, and recurse. That works, but getDepth is itself an O(n) scan, and you call it at every one of the O(log n) levels — so the whole thing is O(n log n). A neat micro-optimization is to prune: fold the height difference into a single boolean so a failure anywhere aborts the rest.

The real fix is sharper and is the session's signature trick: make the height function do double duty. Have it return the height normally, but return -1 the instant it discovers an unbalanced subtree. Because -1 propagates upward — any parent that sees it returns -1 too — a single post-order pass answers the question in O(n).

public boolean isBalanced(TreeNode root) {
    return height(root) != -1;
}

// returns the height, or -1 the moment any subtree is unbalanced
private int height(TreeNode root) {
    if (root == null) return 0;
    int left  = height(root.left);
    int right = height(root.right);
    if (left == -1 || right == -1 || Math.abs(left - right) > 1)
        return -1;                    // short-circuit straight to the top
    return 1 + Math.max(left, right);
}

This is the payoff of the "wall" from the previous section: the balance decision lives exactly at the seam between "both children reported" and "combine." Sentinel-returns-that-propagate is a pattern you will reuse constantly — diameter, path sums, and "is this subtree valid" questions are all the same move.

The Symmetry Family: Invert, Symmetric, Same, Subtree

Four classic problems that look distinct but are one idea — recurse on a pair of nodes and reconcile their base cases. Start with the simplest.

LC 226 Invert Binary Tree — the famous "why can't you invert a binary tree on a whiteboard" problem. Divide-and-conquer makes it three lines: invert both subtrees, then swap them. Returning root at the end is what lets the parent reattach the swapped children.

public TreeNode invertTree(TreeNode root) {
    if (root == null) return root;
    TreeNode left  = invertTree(root.left);
    TreeNode right = invertTree(root.right);
    root.left = right;
    root.right = left;
    return root;                       // must return so the parent can relink
}

// LC 101 — mirror check via an overloaded two-node helper
public boolean isSymmetric(TreeNode root) {
    return root == null || isSymmetric(root.left, root.right);
}
private boolean isSymmetric(TreeNode a, TreeNode b) {
    if (a == null && b == null) return true;   // both empty → fine
    if (a == null || b == null) return false;  // one empty → mismatch
    if (a.val != b.val) return false;
    return isSymmetric(a.left, b.right) && isSymmetric(a.right, b.left);  // mirror
}

LC 101 Symmetric Tree pairs a node's left child with the other's right child (the mirror). LC 100 Same Tree is the identical helper with the pairing straightened out — a.left with b.left, a.right with b.right. Notice the three base cases are the same every time: both null (equal), one null (unequal), values differ (unequal). Learn that triple once and you have written half of every tree-comparison problem.

LC 572 Subtree of Another Tree layers "same tree" inside a traversal: walk every node of the big tree and ask "is the subtree rooted here identical to t?" The one subtlety the notes flag — hitting a null mid-comparison is not automatically a mismatch, because the smaller tree can legitimately end before the big one; that is precisely what the same-tree base cases already handle. It is O(m·n) worst case: an isSame call at every node.

Tweaked Identical (LintCode) generalizes symmetry: at each level the two subtrees may match either straight (same-tree pairing) or crossed (symmetric pairing). So the recurrence ORs the two pairings together. That doubling is expensive — one node spawns four recursive branches, giving 4^log n, and since 4^log n = (2·2)^log n = 2^log n · 2^log n = n · n, the complexity is O(n²). Being able to derive that 4^log n = n² on the spot is exactly the kind of throwaway analysis that impresses interviewers.

Validating a BST (LC 98)

The single most instructive BST problem, because the obvious solution is wrong in an instructive way. The tempting move — at each node check left.val < node.val < right.val — fails, because the BST invariant is about entire subtrees, not immediate children. A node buried deep in the left subtree can still exceed the root, and the local check never looks that far. There are three solid approaches:

1. Inorder to a list, then verify increasing. Flatten the tree with an inorder traversal and confirm every element is strictly greater than the previous. Correct, simple, O(n) time and O(n) space.
2. Pass a (min, max) range down. The root may be anything; its left subtree is bounded above by the root's value, its right subtree bounded below. Shrink the window as you descend and reject any node that violates it. This is the cleanest recursion — note the long bounds to survive Integer.MIN_VALUE / MAX_VALUE node values.
3. Iterative inorder with a running prev. The stack template from earlier, comparing each popped value against the previous — O(n) time, O(h) space, and no full list materialized.

public boolean isValidBST(TreeNode root) {
    return helper(root, Long.MIN_VALUE, Long.MAX_VALUE);
}

private boolean helper(TreeNode root, long min, long max) {
    if (root == null) return true;
    if (root.val <= min || root.val >= max) return false;   // out of allowed window
    return helper(root.left, min, root.val)          // left: cap the max at root
        && helper(root.right, root.val, max);        // right: floor the min at root
}

BST as a Search Structure: Range & Closest Value

The point of a BST is that the ordering invariant lets you prune — the same instinct as binary search, which is why the notes frame a BST as "binary search with pointers." Two problems make it concrete.

Search Range in a BST (LintCode 11) — print every key in [k1, k2] in ascending order. An inorder traversal that prints only in-range values already works in O(n), but you can do better with pruning: only recurse left when the current value could still exceed k1, and only recurse right when it could still be below k2. Whole subtrees that fall outside the window are never touched.

public int closestValue(TreeNode root, double target) {
    int closest = root.val;
    while (root != null) {
        if (Math.abs(root.val - target) < Math.abs(closest - target))
            closest = root.val;                 // track the best seen so far
        if (target < root.val) root = root.left;    // prune the entire other half
        else if (target > root.val) root = root.right;
        else return root.val;                       // exact hit
    }
    return closest;
}

LC 270 Closest BST Value — find the value nearest a target. Because a BST tells you which way to go, you never explore both children: at each node update the best-so-far, then descend left if the target is smaller, right if larger. That is an O(h) walk — O(log n) on a balanced tree — versus O(n) for scanning an unsorted tree. The recursive version is identical in spirit; the iterative one above just avoids the call stack.

One honest limitation from the notes: finding the k-th closest value is not clean on a plain BST, because without parent pointers you cannot easily step outward in both directions from the target. The pragmatic answer is to inorder the tree into an array first and work there — a reminder that the right data structure sometimes means copying into a different one.

Problem Checklist