4.14.2 — Maximum Depth of Binary Tree

LeetCode 104 · Easy · ★ Blind 75

The problem

Return the number of nodes along the longest path from the root down to a leaf.

     3
   /   \
  9    20        →  3
      /   \
    15     7

The pattern

The depth of a tree is one more than the depth of its deeper subtree. That sentence is the code.

\text{depth}(node) = 1 + \max(\text{depth}(left),\ \text{depth}(right))

An empty tree has depth 0, which is the base case.

This is a post-order computation: the node cannot answer until both children have answered. Most tree problems that return a number work this way — the answers flow upwards from the leaves.

The solution

Python

class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        return 1 + max(self.maxDepth(root.left), self.maxDepth(root.right))

TypeScript

function maxDepth(root: TreeNode | null): number {
  if (!root) return 0;
  return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}

That is the entire solution. The base case returning 0 is what makes a leaf come out as 1 + max(0, 0) = 1, which is correct — a single node is a tree of depth 1.

The two iterative versions

Both are worth being able to write, because the choice between them is a real one.

Breadth-first, counting levels. Process the tree one level at a time; the number of levels is the depth.

from collections import deque

def maxDepth(self, root):
    if not root: return 0
    queue = deque([root])
    depth = 0
    while queue:
        depth += 1
        for _ in range(len(queue)):        # exactly one level
            node = queue.popleft()
            if node.left: queue.append(node.left)
            if node.right: queue.append(node.right)
    return depth

The for _ in range(len(queue)) line is the important one, and it recurs throughout this chapter. Capturing the queue's length before the inner loop freezes the current level, so the nodes you add inside the loop belong to the next level and are not processed until the next round. Without it you cannot tell where one level ends.

Depth-first with an explicit stack, pushing (node, depth) pairs and tracking the maximum.

Which traversal, and when

This is the decision that runs through the whole chapter, so it is worth stating once:

• Use DFS when the answer depends on subtrees — depth, sums, paths, validation. Memory is O(h), the height.
• Use BFS when the answer depends on levels, or when you want the shallowest result and can stop early. Memory is O(w), the maximum width.

For a balanced tree the last level holds about half the nodes, so BFS can use O(n) memory while DFS uses O(\log n). For a degenerate tree it is the other way round. That trade is why both exist.

Complexity

O(n) time. O(h) space for the recursion — O(\log n) balanced, O(n) degenerate.

Where this goes next

• Minimum Depth — nearly identical, with one trap: a node with only one child is not a leaf, so min(left, right) would wrongly return 0 for the missing side. BFS is cleaner here anyway, because you can stop at the first leaf you meet.
• Balanced Binary Tree — depth again, but you also need to know whether each subtree was balanced. 4.14.4.
• Diameter — the longest path anywhere, computed from depths. 4.14.3.

Next: 4.14.3 Diameter of Binary Tree — where the answer you return upwards is not the answer the problem wants.