Maximum Depth of Binary Tree

Problem Statement

Given the root of a binary tree, return its maximum depth — the number of nodes along the longest path from the root down to the furthest leaf.

Input:  root = [3, 9, 20, null, null, 15, 7]
Output: 3

        3          ← level 1
       / \
      9   20       ← level 2
         /  \
        15   7     ← level 3

Input:  root = []
Output: 0

Intuition

This is the simplest tree problem there is, and it is worth studying carefully — not for the answer, but because its shape is reused by almost every other tree problem.

Try to solve it by walking the tree and tracking a counter, and it gets fiddly fast: when do you increment? When do you decrement? What resets it?

Now flip the question around.

That single sentence is the whole algorithm. The recursion does the walking; you only describe the relationship between a node and its children.

Why this works without any bookkeeping

Every recursive tree solution needs two things, and no more:

There is no counter to maintain and nothing to reset, because each call returns a finished answer for its own subtree. The call stack handles the position tracking for free.

The real-world version

Imagine asking a company how many levels of management it has. The CEO does not count anything. They ask each direct report "how many levels are under you?", wait for the answers, take the biggest, and add one for themselves.

Every manager does the same. People with no reports answer "zero". The answer assembles itself from the bottom up.

Approach

Watch it run

Solution

class TreeNode:
    def __init__(self, val: int = 0, left: "TreeNode | None" = None,
                 right: "TreeNode | None" = None):
        self.val = val
        self.left = left
        self.right = right


def max_depth(root: TreeNode | None) -> int:
    """Return the number of nodes on the longest root-to-leaf path."""
    # Base case: an empty tree has no levels.
    if root is None:
        return 0

    # Combine step: my depth is one more than my deeper child's.
    return 1 + max(max_depth(root.left), max_depth(root.right))


def max_depth_iterative(root: TreeNode | None) -> int:
    """BFS version — count how many levels the queue produces."""
    from collections import deque

    if root is None:
        return 0

    queue = deque([root])
    depth = 0

    while queue:
        # Fixing the level size BEFORE the loop is what separates the levels.
        for _ in range(len(queue)):
            node = queue.popleft()
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        depth += 1

    return depth

Complexity Analysis

• Time — every node is visited exactly once, and each visit does constant work.
• Space — the recursive version uses the call stack, which holds one frame per level on the current path. That is O(h) where h is the height: about O(log n) for a balanced tree, but O(n) for a tree that is one long chain.

Edge Cases

Related Problems

• Invert Binary Tree — the same recursive skeleton, doing something else at the combine step
• Diameter of Binary Tree — depth again, but tracking a second answer along the way
• Binary Tree Level Order Traversal — the BFS version, keeping each level
• Trees — DFS and BFS side by side