Maximum Depth of Binary Tree

Maximum Depth of a Binary Tree is the classic warm-up for tree recursion. It teaches the single most useful idea for trees: a tree problem is almost always a smaller version of itself on each child, solved by DFS recursion.

The idea

A tree is recursive by nature: every node is itself the root of a smaller subtree. So instead of trying to measure the whole tree at once, ask one small question at each node:

How deep is the subtree that starts here?

The answer is simple. An empty tree (a null child) has depth 0. Any real node is 1 (for itself) plus the depth of its deeper child:

depth(node) = 1 + max(depth(left), depth(right))

That is the whole algorithm. We walk down with recursion until we hit null, then the answers bubble back up: each leaf returns 1, its parent takes the max of its children and adds 1, and so on until the root returns the full depth.

There is no faster approach — we must look at every node once to know it exists — so this clean O(n) recursion is the intended answer.

Walk through it

Step through the animation. The highlight moves down the tree as we call maxDepth on each node (3 → 9, then 3 → 20 → 15, then 20 → 7). When a node finishes, its returned depth appears as a badge and the node turns green. Watch the depths bubble back up: leaves return 1, node 20 returns 2, and the root returns 3.

Pseudocode

function maxDepth(node):
    if node is null:
        return 0                      # empty tree has no depth
    leftDepth  = maxDepth(node.left)  # recurse down the left
    rightDepth = maxDepth(node.right) # recurse down the right
    return 1 + max(leftDepth, rightDepth)   # this node + deeper side

The base case (null → 0) is what stops the recursion. Every other call leans on the answers from its two children.

The Python solution

def max_depth(root):
    if root is None:
        return 0
    left = max_depth(root.left)
    right = max_depth(root.right)
    return 1 + max(left, right)

• Lines 2–3 are the base case: a None node contributes 0 depth and stops the recursion.
• left = max_depth(root.left) recurses all the way down the left subtree before doing anything else.
• right = max_depth(root.right) then does the same for the right subtree.
• Line 6 combines them: 1 for the current node plus the depth of its deeper child. This return value is what the parent call receives.

Complexity

Time is O(n) because we visit all n nodes once. The extra space is O(h), the height of the tree — that is the depth of the recursion call stack. For a balanced tree that is O(log n); for a degenerate (linked-list-shaped) tree it is O(n).

When this pattern shows up

Practice