Maximum Depth of Binary Tree

The problem

Given the root of a binary tree, return its maximum depth — the number of nodes on the longest root-to-leaf path. An empty tree has depth 0; a single-node tree has depth 1.

class Node:
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

Pattern: trees love recursion

Almost every binary-tree problem has a clean recursive solution where the answer at the root is some function of the answers at the left and right subtrees. Maximum depth is the simplest such recurrence: depth(root) = 1 + max(depth(left), depth(right)). Base case: empty tree has depth 0.

Memorize this template. The vast majority of tree problems follow it: define what you need from each subtree, compute it recursively, combine at the root.

Recursive solution

def max_depth(root: Node | None) -> int:
    if root is None:
        return 0
    return 1 + max(max_depth(root.left), max_depth(root.right))

Trace

Tree:        3
            / \
           9  20
              / \
             15  7

max_depth(3)
├── 1 + max(max_depth(9), max_depth(20))
│   ├── max_depth(9):
│   │   ├── 1 + max(max_depth(None), max_depth(None))
│   │   ├── = 1 + max(0, 0) = 1
│   ├── max_depth(20):
│   │   ├── 1 + max(max_depth(15), max_depth(7))
│   │   ├── max_depth(15) = 1, max_depth(7) = 1
│   │   ├── = 1 + max(1, 1) = 2
│   └── = 1 + max(1, 2) = 3

return 3

Iterative (BFS) alternative

Process the tree level by level. Each pass through the while loop is one level. Depth increments per level; the total at the end is the answer.

from collections import deque

def max_depth_bfs(root: Node | None) -> int:
    if root is None:
        return 0
    q = deque([root])
    depth = 0
    while q:
        depth += 1
        for _ in range(len(q)):     # process one level at a time
            node = q.popleft()
            if node.left:  q.append(node.left)
            if node.right: q.append(node.right)
    return depth

Iterative DFS with explicit stack also works, but BFS is the more natural choice when "depth" or "level" is the answer.

Complexity

• Time: O(n) — every node visited once.
• Space: O(h) recursive (stack equal to tree height), O(w) iterative BFS (queue holds at most one level wide). For a balanced tree both are O(log n); for a degenerate chain the recursive version is O(n).

Variations worth knowing

• Minimum Depth of Binary Tree — min instead of max, but careful: at a node with only one child, you must NOT take min(0, depth_of_existing_child) = 0. Handle the "one missing child" case explicitly. BFS short-circuits on the first leaf and is much faster on unbalanced trees.
• Diameter of Binary Tree — the longest path between any two nodes. At each node, the answer through it is depth(left) + depth(right); the global answer is the max over all nodes. Compute both in one post-order traversal.
• Balanced Binary Tree — a tree is balanced iff |depth(left) − depth(right)| ≤ 1 at every node. Single post-order traversal: if any subtree is unbalanced, propagate a −1 sentinel upward and short-circuit.