Maximum Depth of Binary Tree

Problem

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 deepest leaf.

Example: A tree of shape [3, 9, 20, null, null, 15, 7] has max depth 3.

What the interviewer is testing

• Can you write a clean recursion — the "empty is zero, else 1 + max of children" base case?
• Can you also produce a BFS/level-by-level version on demand?
• Do you correctly handle the empty-tree base case?

Recursive DFS — O(n) time, O(h) stack space

The archetypal three-line tree recursion. If the interviewer asks you to write "the simplest possible correct solution," this is the answer.

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

Iterative BFS — O(n) time, O(w) space

Level-by-level walk with a queue, incrementing depth at each level boundary. Useful when the interviewer says "now do it without recursion" or if the tree is very deep (thousands of nodes) and you want to avoid a stack overflow.

from collections import deque

def max_depth(root):
    if root is None:
        return 0
    q = deque([root])
    depth = 0
    while q:
        depth += 1
        for _ in range(len(q)):        # process one whole level
            node = q.popleft()
            if node.left:  q.append(node.left)
            if node.right: q.append(node.right)
    return depth

Complexity — what to say out loud

"Time O(n) either way — every node is visited once. Recursive DFS uses O(h) stack, where h is the tree height (O(log n) for balanced, O(n) worst-case skewed). Iterative BFS uses O(w) queue space, where w is the max width — up to n/2 for a complete tree at the widest level."

Edge cases the interviewer will ask about

• Empty tree — return 0. Base case in both versions handles it.
• Single node — depth 1.
• Skewed tree (all left or all right) — depth n, DFS stack blows up on huge n → use BFS.
• Very wide but shallow — BFS queue is O(n), DFS is cheap.

Common follow-ups

• "Minimum depth" — Distance to nearest leaf. BFS is naturally better here — return as soon as you hit a leaf. DFS needs a special case for when one child is null.
• "Diameter of tree" — Longest path between any two nodes. DFS returning depth to parent; track left + right at each node as a candidate for max.
• "Balanced tree check" — Same recursion pattern, returning either depth or -1 (unbalanced sentinel).

How to verbalize your answer

"The recursive definition is trivial: empty tree is zero, else one plus the deeper of the two children. That's three lines. The iterative version is a BFS with level increments. Time O(n), space O(h) recursive or O(w) BFS. Pick BFS if the tree is very deep and you're worried about stack."