104. Maximum Depth of Binary Tree

If you’ve never written a recursive tree solution, this is the one to start with — the whole answer is a single line that reads like the definition of “depth” itself. It’s the gentlest entry into the binary tree traversal patterns, and the shape you learn here repeats in almost every tree problem that follows.

The problem

Given the root of a binary tree, return its maximum depth: the number of nodes on the longest path from the root down to the farthest leaf. (Full statement on LeetCode.)

A tree that’s just a root with two children has depth 2. An empty tree has depth 0. That empty case is the hinge the whole recursion swings on.

Intuition: a node’s depth is one more than its taller subtree

Don’t think about the whole tree at once. Stand at any single node and ask a smaller question: how deep is the tree rooted here? Whatever the answer is for my left child, and whatever it is for my right child, my own depth is one more than the bigger of the two — because I sit one level above both, and the longest path has to go through the deeper side.

$\text{depth}(node) = 1 + \max\big(\text{depth}(node.left),\; \text{depth}(node.right)\big)$

The recursion bottoms out on nothing: a null pointer is a tree with no nodes, so its depth is 0. That single base case is what makes the +1 land correctly — a leaf’s two null children both report 0, so the leaf reports $1 + \max(0, 0) = 1$, and the counts stack up cleanly all the way to the root.

Solution

The recursive version is a near-transcription of the recurrence above:

class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) return 0;                 // empty tree: no nodes, depth 0
        int left = maxDepth(root.left);
        int right = maxDepth(root.right);
        return 1 + Math.max(left, right);           // this node plus its deeper side
    }
}

That’s the answer you’d write in an interview. But the recursion uses the call stack, and on a badly skewed tree (think a chain of 10,000 nodes) that stack can grow to the full height. If the interviewer pushes on stack safety, switch to a breadth-first sweep that counts levels with an explicit queue:

class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) return 0;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int depth = 0;
        while (!queue.isEmpty()) {
            int levelSize = queue.size();           // nodes sitting on this level
            depth++;                                // finishing a level adds one
            for (int i = 0; i < levelSize; i++) {
                TreeNode node = queue.poll();
                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }
        }
        return depth;
    }
}

Draining the queue one level at a time — snapshotting levelSize before the inner loop — is what lets you bump depth exactly once per level.

Complexity

Approach	Time	Space
Recursive DFS	$O(n)$	$O(h)$
Iterative BFS	$O(n)$	$O(n)$

Both touch every node once, so time is linear. DFS space is the recursion depth $O(h)$ — that’s $O(\log n)$ for a balanced tree but $O(n)$ for a skewed one. BFS holds a whole level in the queue, which can be up to $n/2$ nodes at the bottom of a full tree, so $O(n)$.

In an interview

Say the recurrence out loud before you type: “the depth of a node is one plus the deeper of its two subtrees, and a null subtree has depth 0.” That one sentence proves you found the recursive structure, which is what’s really being graded on an easy tree problem.

The trap here is off-by-one: this problem counts nodes on the path, not edges. If you ever return max(left, right) without the +1, you’re counting edges and every answer drops by one. Naming that distinction — and confirming the null root returns 0, not 1 — heads off the most common bug.

The exact same “solve the children, combine at the parent” recursion drives Invert Binary Tree and the structural check in Same Tree; the level-by-level queue you saw in the BFS version is the whole idea behind Binary Tree Level Order Traversal. The binary tree patterns hub collects where each of these shapes shows up.

References

• LeetCode 104 — Maximum Depth of Binary Tree