Trees I

Part 10. Most tree problems share one shape: recurse on the children, then combine their answers at the current node. Trust the recursion to handle the subtrees; you only define the base case and the combine step. These four drill that reflex.

All examples use the standard node:

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

1. Invert Binary Tree

Swap every left/right pair so the tree becomes its mirror image.

The combine step is literally a swap: invert both subtrees, then exchange the current node's children. Base case: a null node inverts to null.

public TreeNode invertTree(TreeNode root) {
    if (root == null) return null;
    TreeNode left = invertTree(root.left);
    TreeNode right = invertTree(root.right);
    root.left = right;      // swap the (already inverted) children
    root.right = left;
    return root;
}

Because you recurse first and swap after, each subtree is mirrored before it's reattached — the whole tree flips in one post-order pass.

Time: O(n). Space: O(h) recursion, h = height.

Prep note. This is the problem a famous tweet claimed got someone rejected — it's deliberately easy. The point is a clean, confident recursive base case + combine. Nail the shape here; the rest of the section reuses it.

2. Maximum Depth of Binary Tree

Return the number of nodes along the longest root-to-leaf path.

Depth of a node = 1 + the deeper of its two subtrees. Base case: a null node has depth 0.

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

That's the entire algorithm — the combine step is 1 + max(children).

Time: O(n). Space: O(h).

Prep note. The BFS alternative counts levels with a queue and is the honest answer to "do it without recursion" (avoids stack overflow on a degenerate, list-like tree of depth n). Same idea returns for level-order traversal in Part 11.

3. Same Tree

Are two trees structurally identical with equal values?

Compare the roots, then recurse pairwise on left-with-left and right-with-right. Base cases: both null (equal), one null (not), or values differ (not).

public boolean isSameTree(TreeNode p, TreeNode q) {
    if (p == null && q == null) return true;
    if (p == null || q == null || p.val != q.val) return false;
    return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}

The ordering of the base cases matters: check both-null first, then either-null, so the final p.val != q.val only runs when both nodes exist.

Time: O(n). Space: O(h).

Prep note. This exact comparator is the engine for the next problem and for Symmetric Tree (compare left.left with right.right). It's a building block, not a one-off.

4. Subtree of Another Tree

Does root contain a subtree identical to subRoot?

At every node of root, ask "is the tree rooted here the same as subRoot?" using the Same Tree check. Recurse down root until one node matches or you run out.

public boolean isSubtree(TreeNode root, TreeNode subRoot) {
    if (root == null) return false;
    if (isSameTree(root, subRoot)) return true;                 // match anchored here?
    return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);
}

private boolean isSameTree(TreeNode a, TreeNode b) {
    if (a == null && b == null) return true;
    if (a == null || b == null || a.val != b.val) return false;
    return isSameTree(a.left, b.left) && isSameTree(a.right, b.right);
}

It's two nested recursions: one to locate candidate roots, one to verify the match.

Time: O(m·n) worst case. Space: O(h).

Prep note. The O(m+n) upgrade serializes both trees and runs substring search (KMP) — a match becomes a substring test. Mention it as the optimal approach; the nested-recursion version is what you write first.

The pattern, in one line

Nearly every tree problem is recurse on children, combine at the node, with a null base case. Define those two pieces and trust the recursion for everything below. Reusable checks (like Same Tree) become the building blocks of harder ones.

Next in Part 11: Trees II — BFS level order, BST validation, and in-order's sorted magic.