10 — Trees & Binary Search Trees

What a binary tree is

A binary tree is nodes, each with up to two children — left and right. One node is the root; nodes with no children are leaves.

        1          <- root, depth 0
       / \
      2   3        <- depth 1
     / \
    4   5          <- leaves at depth 2

Vocabulary you'll need:

• Height / depth — the number of edges on the longest path from a node down to a leaf. A single node has height 0; an empty tree has height −1 or 0 by convention (state which you're using).
• Balanced — every node's two subtrees differ in height by at most 1. A balanced tree of n nodes has height O(log n).
• Skewed — every node has one child, so it's effectively a linked list with height n − 1. This is the worst case for every tree algorithm.

Why complexity is usually written with h: tree operations cost O(h), and h ranges from log n (balanced) to n (skewed). Always give both bounds — "O(h), which is O(log n) balanced and O(n) in the skewed worst case."

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

The one question that solves most tree problems

What does each node need from its children, and what does it return to its parent?

Answer that in a sentence and the code writes itself. Most of this file is variations on that question.

Traversals

A traversal visits every node. The three DFS orders differ only in when you process the current node relative to recursing.

void preorder(TreeNode n) {
    if (n == null) return;
    visit(n);                      // node FIRST
    preorder(n.left);
    preorder(n.right);
}

void inorder(TreeNode n) {
    if (n == null) return;
    inorder(n.left);
    visit(n);                      // node in the MIDDLE
    inorder(n.right);
}

void postorder(TreeNode n) {
    if (n == null) return;
    postorder(n.left);
    postorder(n.right);
    visit(n);                      // node LAST
}

On this tree:

        1
       / \
      2   3
     / \
    4   5

Choosing a traversal

The organizing principle:

• Preorder = information flows DOWN via parameters (you pass context to children).
• Postorder = information flows UP via return values (children report to you).

Most "hard" tree problems need both at once — see Pattern 2.

Iterative inorder

Needed when recursion depth is a concern, and for Kth Smallest where you want to stop early.

Deque<TreeNode> stack = new ArrayDeque<>();
TreeNode cur = root;
while (cur != null || !stack.isEmpty()) {
    while (cur != null) { stack.push(cur); cur = cur.left; }   // dive as far left as possible
    cur = stack.pop();                                          // the leftmost unvisited node
    visit(cur);
    cur = cur.right;                                            // now handle its right subtree
}

The stack is doing by hand exactly what recursion does automatically: remembering the nodes you passed on the way down so you can return to them.

BFS — the level-size loop

Breadth-first search visits nodes level by level, using a queue. It's the single most important template after plain recursion.

List<List<Integer>> res = new ArrayList<>();
if (root == null) return res;

Queue<TreeNode> q = new ArrayDeque<>();
q.offer(root);

while (!q.isEmpty()) {
    int size = q.size();                 // MUST be captured before the inner loop
    List<Integer> level = new ArrayList<>();

    for (int i = 0; i < size; i++) {
        TreeNode node = q.poll();
        level.add(node.val);
        if (node.left != null)  q.offer(node.left);
        if (node.right != null) q.offer(node.right);
    }
    res.add(level);
}
return res;

Why int size = q.size() must be captured first

At the top of each outer iteration, the queue contains exactly one level. Capturing size freezes that count, so the inner loop processes precisely those nodes — and the children it enqueues become the next level.

If you instead wrote for (int i = 0; i < q.size(); i++), the size would grow as you add children, and levels would blur together.

Trace:

Result: [[1], [2,3], [4,5]]. ✓

Derived problems — all one-line edits

• Right Side View: take i == size - 1 from each level (the last node processed).
• Maximum Depth: count outer iterations.
• Minimum Depth: return at the first level containing a leaf.

Say "this is level-order traversal with one line changed" rather than presenting each as a new algorithm.

Pattern 1 — pure recursion, return the answer directly

When the answer at a node is a clean function of the children's answers, recursion is nearly transparent.

int maxDepth(TreeNode root) {
    if (root == null) return 0;                                    // base case
    return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}

Read it as: "my depth is 1 (me) plus the deeper of my two subtrees." The base case says an empty tree has depth 0.

TreeNode invertTree(TreeNode root) {
    if (root == null) return null;
    TreeNode left = invertTree(root.left);     // save before overwriting
    root.left = invertTree(root.right);
    root.right = left;
    return root;
}

The temporary is needed for the same reason as in linked-list reversal: the first assignment destroys what the second one needs.

boolean isSameTree(TreeNode p, TreeNode q) {
    if (p == null && q == null) return true;    // both empty — equal
    if (p == null || q == null) return false;   // exactly one empty — unequal
    return p.val == q.val
        && isSameTree(p.left, q.left)
        && isSameTree(p.right, q.right);
}

Those two null checks, in that order, are the template for every paired-tree comparison. Both null → equal. Exactly one null → unequal. Only then is it safe to read .val.

Subtree of Another Tree — composing them

boolean isSubtree(TreeNode root, TreeNode sub) {
    if (root == null) return false;
    if (isSameTree(root, sub)) return true;                     // match rooted here?
    return isSubtree(root.left, sub) || isSubtree(root.right, sub);   // else try children
}

O(m · n) worst case — at each of m nodes you may compare n nodes.

The O(m + n) alternative: serialize both trees to strings with null markers, then run substring search. Mention it if pushed. The null markers are essential — without them, different trees can serialize identically.

Pattern 2 — return one thing, record another

This is the most important tree pattern, and the one that separates comfortable candidates from struggling ones.

The situation

Sometimes the value your parent needs is not the answer you're computing.

Take Diameter of Binary Tree: the longest path between any two nodes.

At a node, the longest path through that node is leftHeight + rightHeight. But your parent can't use that number — it needs your height to compute its own path. Two different quantities.

The solution

Return the height. Record the diameter in a field.

private int best = 0;

public int diameterOfBinaryTree(TreeNode root) {
    best = 0;                            // reset — the field may hold a previous run's value
    height(root);
    return best;
}

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

    best = Math.max(best, l + r);        // path THROUGH this node — the ANSWER
    return 1 + Math.max(l, r);           // height — what the PARENT needs
}

Trace on:

        1
       / \
      2   3
     / \
    4   5

Answer: 3 — the path 4 → 2 → 1 → 3, which has 3 edges. ✓

Notice the diameter's best path doesn't pass through the root's return value at all; it was recorded as a side effect. That's the pattern.

Java needs a field (or a one-element array) for this because primitives are passed by value — see 03.

Binary Tree Maximum Path Sum — identical shape

A path can start and end anywhere. Node values may be negative.

private int best;

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

private int gain(TreeNode node) {
    if (node == null) return 0;
    int l = Math.max(gain(node.left), 0);    // CLAMP: a negative branch is better skipped
    int r = Math.max(gain(node.right), 0);

    best = Math.max(best, node.val + l + r); // best path BENDING at this node
    return node.val + Math.max(l, r);        // a path the parent can EXTEND uses one side only
}

Two things to say aloud:

1. The Math.max(..., 0) clamp. If a subtree's best contribution is negative, you simply don't take it — treat it as contributing 0. That's why negative values don't poison the answer.

2. Why the return uses one side but the record uses both. A path recorded at this node may bend — come up the left, through the node, down the right. But a path your parent extends must pass through you and continue upward, so it can only use one of your branches. Two different quantities, exactly as in Diameter.

best starts at Integer.MIN_VALUE, not 0, because an all-negative tree's answer is its largest (least negative) single node.

Balanced Binary Tree — the sentinel variant

The naive version is O(n²): at every node, call height on both subtrees, each of which walks the whole subtree.

The fix: have height return -1 to mean "unbalanced somewhere below", so one traversal does both jobs.

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

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

    int l = height(node.left);
    if (l == -1) return -1;                        // propagate failure, stop early

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

    if (Math.abs(l - r) > 1) return -1;            // imbalance found HERE
    return 1 + Math.max(l, r);
}

Encoding a failure signal inside the return channel is the reusable idea. Since a real height is never negative, -1 is free to mean something else. That turns O(n²) into O(n). Naming both complexities is the point of the question.

Pattern 3 — pass state down (preorder)

When a node's validity depends on its ancestors, thread that context through parameters.

Count Good Nodes

A node is "good" if no node on the path from the root to it has a greater value.

private int count = 0;

public int goodNodes(TreeNode root) {
    count = 0;
    dfs(root, Integer.MIN_VALUE);
    return count;
}

private void dfs(TreeNode node, int maxSoFar) {
    if (node == null) return;
    if (node.val >= maxSoFar) count++;
    int newMax = Math.max(maxSoFar, node.val);   // extend the context for children
    dfs(node.left, newMax);
    dfs(node.right, newMax);
}

Each node receives "the largest value on the path down to me" and passes an updated version to its children. Pure information-flows-down.

Validate BST — the archetype

First, what a BST is: a binary tree where for every node, all values in its left subtree are smaller, and all values in its right subtree are larger.

The bug everyone writes:

// WRONG
return node.left.val < node.val && node.right.val > node.val && recurse...;

It only checks immediate children. This tree passes that check and is not a BST:

        5
       / \
      1   7
         / \
        3   8      <- 3 is in 5's RIGHT subtree but 3 < 5

Locally, 3 < 7 and 7 > 5 are both fine. Globally it's invalid.

The fix — carry an open interval down:

public boolean isValidBST(TreeNode root) {
    return valid(root, null, null);          // no bounds at the root
}

private boolean valid(TreeNode node, Integer low, Integer high) {
    if (node == null) return true;
    if (low != null && node.val <= low) return false;
    if (high != null && node.val >= high) return false;

    return valid(node.left,  low, node.val)      // going LEFT tightens the upper bound
        && valid(node.right, node.val, high);    // going RIGHT tightens the lower bound
}

Tracing the bad tree: at node 7, bounds are (5, ∞). Descending left to node 3, bounds become (5, 7). Check 3 <= 5 → false returned. ✓

Why boxed Integer rather than int sentinels: a node may legitimately hold Integer.MIN_VALUE, so using that as "no lower bound" would wrongly reject it. null means "unbounded" unambiguously. Widening to long bounds works too.

Alternative: do an inorder traversal and verify the values come out strictly increasing. Equally good — inorder on a valid BST is sorted by definition.

BST-specific mechanics

The BST ordering lets you descend without exploring both sides, turning O(n) into O(h).

Lowest Common Ancestor in a BST

TreeNode cur = root;
while (cur != null) {
    if (p.val < cur.val && q.val < cur.val)      cur = cur.left;   // both smaller — go left
    else if (p.val > cur.val && q.val > cur.val) cur = cur.right;  // both larger — go right
    else return cur;                                               // they SPLIT here
}
return null;

Why the split point is the answer: if p and q fall on opposite sides of cur (or one is cur), then cur is on the path to both, and no node below it can be — going either way abandons one of them. So cur is the lowest common ancestor.

O(h) time, O(1) space iteratively.

Kth Smallest in a BST

Inorder yields sorted order, so stop at the kth:

Deque<TreeNode> stack = new ArrayDeque<>();
TreeNode cur = root;
while (cur != null || !stack.isEmpty()) {
    while (cur != null) { stack.push(cur); cur = cur.left; }
    cur = stack.pop();
    if (--k == 0) return cur.val;         // the kth node visited in sorted order
    cur = cur.right;
}
return -1;

Why iterative matters here: it stops after visiting k nodes. Recursive inorder would traverse the whole tree unless you add early-exit plumbing. Cost is O(h + k), not O(n).

Follow-up — "what if kthSmallest is called often?" Augment each node with its subtree size. Then you can navigate directly to the kth in O(h) per query, at the cost of maintaining sizes on insert/delete. Having that answer ready is a strong signal.

Construction from traversals

Build a tree from its preorder and inorder sequences.

The insight:

• Preorder's first element is always the root.
• Inorder splits at the root: everything left of it is the left subtree, everything right is the right subtree.

preorder = [3, 9, 20, 15, 7]        root is 3
inorder  = [9, 3, 15, 20, 7]        9 | 3 | 15, 20, 7
                                    ^left    ^right

Recurse on each side.

private Map<Integer, Integer> inorderIndex = new HashMap<>();
private int preIdx = 0;

public TreeNode buildTree(int[] preorder, int[] inorder) {
    for (int i = 0; i < inorder.length; i++) inorderIndex.put(inorder[i], i);
    preIdx = 0;
    return build(preorder, 0, inorder.length - 1);
}

private TreeNode build(int[] preorder, int left, int right) {
    if (left > right) return null;

    int rootVal = preorder[preIdx++];          // consume the next preorder value
    TreeNode root = new TreeNode(rootVal);
    int mid = inorderIndex.get(rootVal);       // find the split point in O(1)

    root.left  = build(preorder, left, mid - 1);    // MUST be first
    root.right = build(preorder, mid + 1, right);
    return root;
}

The left call must come before the right call. preIdx is a shared cursor consuming preorder left-to-right, and preorder lists the entire left subtree before any of the right. Swapping those two lines compiles fine and silently builds the wrong tree.

The index map is what makes it O(n). Without it you'd scan inorder for the root each time — O(n²).

Serialize and Deserialize

Convert a tree to a string and back.

Why null markers are mandatory

Preorder alone is ambiguous. Both of these have preorder [1, 2]:

    1          1
   /            \
  2              2

The markers make the encoding a bijection — one string, one tree. Raise this proactively; it's the conceptual core of the question.

public String serialize(TreeNode root) {
    StringBuilder sb = new StringBuilder();
    ser(root, sb);
    return sb.toString();
}

private void ser(TreeNode node, StringBuilder sb) {
    if (node == null) { sb.append("N,"); return; }     // explicit null marker
    sb.append(node.val).append(',');
    ser(node.left, sb);
    ser(node.right, sb);
}

public TreeNode deserialize(String data) {
    return des(new ArrayDeque<>(Arrays.asList(data.split(","))));
}

private TreeNode des(Deque<String> tokens) {
    String tok = tokens.poll();
    if ("N".equals(tok)) return null;
    TreeNode node = new TreeNode(Integer.parseInt(tok));
    node.left  = des(tokens);          // same left-then-right ordering discipline
    node.right = des(tokens);
    return node;
}

The tree 1 / 2 \ 3 serializes to "1,2,N,N,3,N,N,". Deserialization consumes tokens in exactly the order serialization produced them, so the structure rebuilds itself.

Level-order with markers works too and is easier to eyeball; preorder is less code.

Recognition checklist

Complexity summary

h = height: O(log n) balanced, O(n) skewed. Give both.