LeetCode 104 – Maximum Depth of Binary Tree

Maximum Depth is three lines and is on every list because it is the smallest problem where the recursive shape of tree algorithms is visible. It is also the setup for a trap: the obvious adaptation to minimum depth is wrong, and seeing why is worth far more than solving this.

The problem

Return the maximum depth of a binary tree — the number of nodes along the longest path from the root down to a leaf.

      3
     / \        -> 3
    9   20
       /  \
      15   7

  []            -> 0
  [1]           -> 1
  [1,null,2]    -> 2

Depth is counted in nodes, not edges, so a single node has depth 1. Both conventions exist in textbooks; check which one is meant when the problem does not say.

The recursion

The depth of a tree is one — for the root — plus the depth of its deeper subtree:

depth(null) = 0
depth(node) = 1 + max(depth(node.left), depth(node.right))

The base case does the work that makes this clean. Returning 0 for a null means a leaf computes 1 + max(0, 0) = 1 automatically, with no separate leaf case. Adding one would be a common instinct and produces a tree one deeper than it is.

Java

class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) return 0;      // an empty tree has depth 0; leaves fall out of this
        return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
    }
}

There is no accumulator, no visited set and no wrapper method. When a tree problem can be written in this shape — a base case for null and one line combining the children — that is almost always the answer, and reaching for a helper with extra parameters is a sign of over-thinking.

Python

class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        if root is None:
            return 0
        return 1 + max(self.maxDepth(root.left), self.maxDepth(root.right))

Why minimum depth is not the mirror image

This is the part to have ready, because it is the natural follow-up (Minimum Depth of Binary Tree, 111) and the obvious edit is wrong:

    1
     \        1 + min(depth(null), depth(2))
      2       = 1 + min(0, 1)
              = 1                        WRONG -- the answer is 2

Minimum depth is the shortest path to a leaf, and a node with one child is not a leaf. The null side returns 0, min takes it, and the recursion reports a path that ends in mid-air. max never has this problem because the null branch is the one it discards.

The fix is to handle the one-child case explicitly — if a child is missing, take the other side rather than the minimum. Volunteering this contrast unprompted is a strong signal: it shows you know why the code works rather than that it does.

The iterative versions

Recursion is O(h) stack, which overflows on a degenerate tree of a hundred thousand nodes. BFS counts levels instead and is the cleanest alternative:

    def maxDepthBfs(self, root: TreeNode) -> int:
        from collections import deque

        if root is None:
            return 0

        depth, queue = 0, deque([root])

        while queue:
            depth += 1
            for _ in range(len(queue)):        # one whole level, as in problem 102
                node = queue.popleft()
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)

        return depth

This is Level Order Traversal with the values thrown away and a counter kept — the same level-size snapshot doing the same job.

Its space is O(w) rather than O(h), which is the trade to name: BFS is better on a deep narrow tree, DFS on a shallow wide one. For minimum depth BFS is categorically better, because it can return the instant it meets the first leaf instead of exploring everything.

Complexity

Every node must be visited: the deepest leaf could be anywhere, so no correct algorithm inspects fewer than all of them.

The pattern

"Return a value up from each subtree, combine at the node" is the single most common tree recursion. Balanced Binary Tree (110) computes this depth and checks a condition on the way back up. Diameter (543) returns depth while recording something else globally — the same skeleton with an extra channel. Binary Tree Maximum Path Sum (124) is the hard version of that idea.

All of them are this function with more happening at the combine step, which is why it is worth being able to write without thinking.

What the interviewer is checking

• The null base case returning 0, and that leaves need no separate case.
• Nodes versus edges, and that you ask if the problem is ambiguous.
• The empty tree.
• That you know the recursion is O(h) stack and what breaks it.
• That you can give the BFS version and state the O(h) versus O(w) trade.
• Bonus, and the real signal: why min does not simply replace max.