Binary Trees — Recursion Given Form

Trees are where recursion stops being abstract. Every tree problem is a recursion problem. Once you stop trying to trace the full execution and start trusting the recursive call, trees become one of the most satisfying categories in DSA.

The mental shift you need: a tree node doesn’t care about the whole tree. It asks its left child for an answer, asks its right child for an answer, combines them, and reports up. That’s the whole pattern. Almost every tree problem is a variation of this.

---

Tree Anatomy

        1          ← root (depth 0, height 3)
       / \
      2   3        ← depth 1
     / \   \
    4   5   6      ← depth 2 (leaves: 4, 5, 6)

• Root: the topmost node, no parent

• Leaf: a node with no children

• Height of a node: longest path from that node down to any leaf. Height of leaf = 0. Height of null = -1 (the convention that makes formulas clean).

• Depth of a node: distance from the root down to that node

• Subtree rooted at N: N plus all its descendants

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

---

Traversals

Three DFS orders, one BFS order. Know all four cold — interviewers ask for them by name and expect both recursive and iterative versions.

The naming convention is about when you visit the Node relative to its Left and Right subtrees:

Traversal	Visit Order	Primary Use
Inorder (LNR)	Left → Node → Right	BST sorted order, expression trees
Preorder (NLR)	Node → Left → Right	Serialize a tree, copy structure
Postorder (LRN)	Left → Right → Node	Delete a tree, compute subtree-up values
Level-order (BFS)	Level by level	Shortest path, zigzag, right-side view

---

Recursive Implementations

The recursive versions are the natural expression of the definition. Write these without thinking:

void inorder(TreeNode node) {
    if (node == null) return;        // base case: nothing to visit
    inorder(node.left);              // L
    System.out.print(node.val);      // N
    inorder(node.right);             // R
}

void preorder(TreeNode node) {
    if (node == null) return;
    System.out.print(node.val);      // N
    preorder(node.left);             // L
    preorder(node.right);            // R
}

void postorder(TreeNode node) {
    if (node == null) return;
    postorder(node.left);            // L
    postorder(node.right);           // R
    System.out.print(node.val);      // N
}

---

Iterative Inorder (Using an Explicit Stack)

The iterative version is worth knowing because interviewers ask for it, and because it exposes exactly what the recursive call stack was doing invisibly.

List<Integer> inorderIterative(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    Deque<TreeNode> stack = new ArrayDeque<>();
    TreeNode curr = root;

    while (curr != null || !stack.isEmpty()) {
        // Phase 1: go as far left as possible, pushing onto stack
        while (curr != null) {
            stack.push(curr);
            curr = curr.left;
        }
        // Phase 2: backtrack to parent, process it, then go right
        curr = stack.pop();
        result.add(curr.val);
        curr = curr.right;
    }
    return result;
}

The outer loop condition curr != null || !stack.isEmpty() is the invariant. It handles two states:

• curr != null: we have a node to descend into

• curr == null but stack non-empty: we’ve hit a leaf, need to backtrack

What most people get wrong: they write while (!stack.isEmpty()) and miss the case where curr is non-null but the stack is empty (the very start, or after popping the rightmost node). The double condition handles both.

---

BFS / Level-Order Traversal

BFS uses a queue. The reason it gives you levels naturally: everything enqueued at any moment belongs to the same generation. Process that generation completely, then the next generation gets enqueued.

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 levelSize = queue.size();      // CRITICAL: snapshot size before expanding
        List<Integer> level = new ArrayList<>();

        for (int i = 0; i < levelSize; 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;
}

The int levelSize = queue.size() snapshot is the mechanism that separates levels. Without it, you’d process everything as one flat list because nodes from the next level get enqueued during the current level’s processing.

---

The Return Value Pattern

This is the single most important concept for tree recursion. Once you internalize it, ~80% of tree problems become variations on a theme.

Most tree problems follow this template:

At each node: ask left subtree for its answer. Ask right subtree for its answer. Combine with the current node’s value. Return something useful upward.

ReturnType solve(TreeNode node) {
    if (node == null) return baseCase;         // what does null contribute?

    ReturnType left  = solve(node.left);       // delegate to left subtree
    ReturnType right = solve(node.right);      // delegate to right subtree

    return combine(left, right, node.val);     // combine and report up
}

The key decision at each problem: what does the function return? Get that right and the combination step usually writes itself.

---

Key Tree Problems with Derivations

1. Maximum Depth (LC 104)

The function returns the height of the subtree rooted at this node.

int maxDepth(TreeNode node) {
    if (node == null) return 0;
    int left  = maxDepth(node.left);
    int right = maxDepth(node.right);
    return Math.max(left, right) + 1;   // deeper subtree + this node
}

Null contributes 0. A leaf contributes 1. Every other node contributes 1 + max of children.

---

2. Diameter of Binary Tree (LC 543)

This is the problem that separates people who’ve genuinely understood the return-value pattern from those who memorized it.

Diameter through a node = height of its left subtree + height of its right subtree. But the diameter of the whole tree might not pass through the root — it could be entirely inside the left or right subtree.

Solution: the function returns height to its parent (for combining). It also updates a global maximum as a side effect.

int maxDiameter = 0;  // global: diameter can be anywhere in tree

int height(TreeNode node) {
    if (node == null) return 0;
    int left  = height(node.left);
    int right = height(node.right);

    // Update global diameter at this node (doesn't propagate up as diameter)
    maxDiameter = Math.max(maxDiameter, left + right);

    // Return HEIGHT (not diameter) to parent
    return Math.max(left, right) + 1;
}

The function has two jobs: (1) return height to parent for the computation above, and (2) update the global answer as a side effect. These are different things. Mixing them up — trying to return diameter and then combine — breaks the aggregation.

---

3. Path Sum (LC 112)

Does any root-to-leaf path sum to the target?

boolean hasPathSum(TreeNode node, int remaining) {
    if (node == null) return false;
    remaining -= node.val;
    if (node.left == null && node.right == null) {  // leaf node
        return remaining == 0;
    }
    return hasPathSum(node.left, remaining) || hasPathSum(node.right, remaining);
}

The leaf check (left == null && right == null) is essential. Without it, null nodes would be counted as valid endpoints.

---

4. Lowest Common Ancestor (LC 236)

Given two nodes p and q (guaranteed to exist in the tree), find their LCA. No parent pointers available.

The insight: if you find p in the left subtree and q in the right subtree (or vice versa), then the current node is the LCA. If both are in the same subtree, recurse into that subtree and it’ll return the LCA from below.

TreeNode lca(TreeNode node, TreeNode p, TreeNode q) {
    if (node == null)             return null;   // exhausted this path
    if (node == p || node == q)   return node;   // found one of the targets

    TreeNode left  = lca(node.left,  p, q);
    TreeNode right = lca(node.right, p, q);

    if (left != null && right != null) return node;   // p and q in different subtrees
    return left != null ? left : right;               // both in same subtree — bubble up
}

The trust required here is real: when lca(node.left, p, q) returns non-null, you’re trusting it found something relevant. You don’t need to know what — just whether it found something.

---

5. Balanced Binary Tree (LC 110)

A tree is height-balanced if for every node, |height(left) - height(right)| ≤ 1.

The naive approach — compute height separately for every node — is O(n²). The efficient approach: return -1 as a sentinel for “this subtree is unbalanced” and short-circuit immediately.

int checkHeight(TreeNode node) {
    if (node == null) return 0;

    int left = checkHeight(node.left);
    if (left == -1) return -1;          // propagate failure up immediately

    int right = checkHeight(node.right);
    if (right == -1) return -1;

    if (Math.abs(left - right) > 1) return -1;   // unbalanced at this node

    return Math.max(left, right) + 1;  // balanced: return actual height
}

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

This is O(n) — each node visited exactly once. The -1 sentinel lets the algorithm abort entire subtrees the moment a violation is found.

---

6. Serialize and Deserialize Binary Tree (LC 297)

Preorder traversal with null markers encodes the complete tree structure. Any other traversal either loses structure (inorder alone can’t reconstruct a unique tree) or requires two traversals.

// Serialize: preorder with "#" for null, "," as separator
String serialize(TreeNode root) {
    if (root == null) return "#";
    return root.val + "," + serialize(root.left) + "," + serialize(root.right);
}

// Deserialize: consume tokens in preorder order
TreeNode deserialize(String data) {
    Queue<String> tokens = new LinkedList<>(Arrays.asList(data.split(",")));
    return build(tokens);
}

TreeNode build(Queue<String> tokens) {
    String val = tokens.poll();
    if (val.equals("#")) return null;           // null marker
    TreeNode node = new TreeNode(Integer.parseInt(val));
    node.left  = build(tokens);                 // build left subtree first
    node.right = build(tokens);                 // then right
    return node;
}

The key: deserialize in the same order you serialized (preorder). Each null marker tells you exactly where a subtree ends — no ambiguity.

---

Height-Balanced Trees: Why AVL and Red-Black Exist

In a perfectly balanced binary tree with n nodes, height = O(log n). Operations are O(log n). Insert elements in sorted order (1, 2, 3, …) and you get a linked list — height O(n), operations O(n). All the benefits of a BST vanish.

AVL trees and Red-Black trees maintain balance through rotations after insert/delete. A rotation is O(1) — it rewires 3 pointers. You don’t need to implement rotations for LeetCode, but understand:

• AVL trees guarantee height ≤ 1.44 log₂(n)

• Java’s TreeMap and TreeSet use Red-Black trees internally

• When an interviewer asks “what’s the time complexity of your BST operation?” the correct answer references whether the tree is balanced

---

Practice Problems

#	Problem	Difficulty	Core Pattern
1	LC 226 — Invert Binary Tree	Easy	Recursive swap left and right
2	LC 572 — Subtree of Another Tree	Easy	Recursive structural equality
3	LC 112 — Path Sum	Easy	DFS with remaining target
4	LC 102 — Level Order Traversal	Medium	BFS with level snapshot
5	LC 105 — Construct from Preorder+Inorder	Medium	Divide-and-conquer on index
6	LC 124 — Binary Tree Maximum Path Sum	Medium	Global max + local linear return
7	LC 543 — Diameter of Binary Tree	Medium	Global max + height return
8	LC 236 — LCA of Binary Tree	Hard	Recursive bubble-up on found nodes

Work problems 1-3 first — each should take under 15 minutes. If problems 6-7 don’t click, re-read the diameter derivation above. The return-value vs. global-accumulator split is the concept to absorb there.

---

Navigation

← Previous	02 — Divide and Conquer
→ Next	04 — Binary Search Trees
↑ Phase Home	Phase 2 README
⌂ Root	Master README