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 — values never matter; only shape does.

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

There is no meaningful brute force distinct from the solution — every node must be seen at least once, so every correct algorithm is Ω(n) — and the ladder starts at the canonical recursion.

The insight: depth is recursively self-similar — the deepest path from the root is one node (the root) plus the deeper of the two subtrees’ deepest paths. Depth-first search (DFS), the traversal that fully explores a branch before backtracking, evaluates exactly that.

# 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


class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        return 1 + max(self.maxDepth(root.left), self.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 insight: the maximum depth is simply how many levels the tree has. Breadth-first search (BFS), the queue-driven traversal that visits the tree ring by ring, counts one level per round: snapshot the queue length, pop exactly that many, 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


class Solution:
    def maxDepth(self, 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

The insight: recursion’s implicit call stack can be replaced by an explicit stack that carries each node tagged with its own depth — the standard recursion-elimination trick, and the safest habit when trees 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


class Solution:
    def maxDepth(self, 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.