Maximum Depth of Binary Tree

Problem

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

Examples

Example 1

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

        3
       / \
      9  20
        /  \
       15   7

Output: 3

The longest root-to-leaf paths (3→20→15, 3→20→7) contain 3 nodes.

Example 2

Input:  root = [1,null,2]
Output: 2

The only path is 1 → 2.

Example 3

Input:  root = []
Output: 0

No nodes, depth 0.

Constraints

• The number of nodes is in [0, 10^4] — a single O(n) traversal is expected.
• -100 <= Node.val <= 100 — only the tree’s shape matters, not the values.

Think about it first

TL;DR

One-line recursive DFS 1 + max(left, right) — O(n) time, O(h) space; BFS level counting is the classic iterative alternative.

Approach 1 — Recursive DFS

Every node must be visited at least once, so every correct algorithm is Ω(n). There is no faster brute force to improve on; the recursion below is the canonical solution.

The depth of a tree is one node (the root) plus the deeper of its two subtrees. This is a recurrence, and depth-first search (DFS) — the traversal that fully explores a branch before backtracking — evaluates it directly.

The tree from example 1 has three levels, so its depth is 3:

flowchart TD
    A[3] --> B[9]
    A --> C[20]
    C --> D[15]
    C --> E[7]

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

from typing import Optional


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

Walkthrough on [3,9,20,null,null,15,7] (example 1): maxDepth(9) = 1 + max(0, 0) = 1; maxDepth(15) = maxDepth(7) = 1; maxDepth(20) = 1 + max(1, 1) = 2; maxDepth(3) = 1 + max(1, 2) = 3.

Complexity: O(n) time — each node contributes O(1) work. O(h) recursion stack: O(log n) for a balanced tree, O(n) for a skewed one.

Approach 2 — Iterative BFS (count the levels)

The maximum depth equals the number of levels in the tree. Breadth-first search (BFS), the queue-driven traversal that visits the tree level by level, counts one level per round: snapshot the current queue length, pop exactly that many nodes, and increment the counter.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

from collections import deque
from typing import Optional


def maxDepth(root: Optional[TreeNode]) -> int:
    if not root:
        return 0
    depth = 0
    queue = deque([root])
    while queue:
        depth += 1
        for _ in range(len(queue)):
            node = queue.popleft()
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
    return depth

Walkthrough on example 1: round 1 pops [3], pushes 9, 20 → depth 1; round 2 pops [9, 20], pushes 15, 7 → depth 2; round 3 pops [15, 7], pushes nothing → depth 3; queue empty, return 3.

Complexity: O(n) time; O(w) space where w is the maximum level width (up to n/2 for a complete tree).

Approach 3 — Iterative DFS with (node, depth) pairs

Replace recursion’s implicit call stack with an explicit stack that carries each node tagged with its own depth. This is the standard way to eliminate recursion, and it avoids stack overflow when a tree may be ~10^4 deep (beyond Python’s default recursion limit of ~1000).

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

from typing import Optional


def maxDepth(root: Optional[TreeNode]) -> int:
    if not root:
        return 0
    best = 0
    stack = [(root, 1)]
    while stack:
        node, depth = stack.pop()
        best = max(best, depth)
        if node.left:
            stack.append((node.left, depth + 1))
        if node.right:
            stack.append((node.right, depth + 1))
    return best

Walkthrough on [1,null,2] (example 2): pop (1, 1) → best 1, push (2, 2); pop (2, 2) → best 2; stack empty, return 2.

Complexity: O(n) time, O(h) stack space.

Common pitfalls

• Node count vs edge count: this problem counts nodes (single node → 1); the near-identical “height in edges” convention would answer 0 — state which convention you’re using.
• Forgetting depth(None) = 0, which both anchors the recursion and handles the empty-tree input.
• On a skewed 10^4-node tree, plain Python recursion can hit the default recursion limit — mention the iterative variant (or sys.setrecursionlimit) before the interviewer does.
• In the BFS version, forgetting the len(queue) snapshot turns level counting into node counting.

Pattern takeaway

f(node) = combine(f(node.left), f(node.right)) with a base case at None is the fundamental tree recursion template — depth is its “hello world” (combine = 1 + max). Master mapping this template to its two iterative forms: BFS with level snapshots when the answer is per-level, and a stack of (node, state) pairs when each path carries its own running state.