104. Maximum Depth of Binary Tree (Easy)

Problem

Given the root of a binary tree, return its maximum depth, the number of nodes along the longest path from the root to a leaf.

Example

• root = [3,9,20,null,null,15,7] → 3
• root = [1,null,2] → 2

LeetCode 104 · Link · Easy

Approach 1: Recursive DFS (canonical one-liner)

Depth of a node is 1 + max depth of its children.

def max_depth(root):
    if not root:
        return 0                                           # L1: base case
    return 1 + max(max_depth(root.left), max_depth(root.right))  # L2: recurse both children

Where the time goes, line by line

Variables: n = number of nodes in the tree, h = tree height, w = max tree width.

Line	Per-call cost	Times executed	Contribution
L1 (base case)	O(1)	n+1 null checks	O(n)
L2 (recurse + max)	O(1) per node	n	O(n) ← dominates (both lines tie)

Every node triggers exactly two recursive calls (left, right) and one max. No node is visited more than once because the recursion tree mirrors the tree structure.

Complexity

• Time: O(n), driven by L2 visiting each node once.
• Space: O(h) recursion.

Approach 2: BFS level count

Count levels with a queue.

from collections import deque

def max_depth(root):
    if not root:
        return 0
    q = deque([root])   # L1: O(1) init
    depth = 0
    while q:
        depth += 1                      # L2: O(1) increment per level
        for _ in range(len(q)):
            node = q.popleft()          # L3: O(1) dequeue
            if node.left:
                q.append(node.left)     # L4: O(1) enqueue
            if node.right:
                q.append(node.right)    # L5: O(1) enqueue
    return depth

Where the time goes, line by line

Variables: n = number of nodes in the tree, h = tree height, w = max tree width.

Line	Per-call cost	Times executed	Contribution
L2 (depth++)	O(1)	h levels	O(h)
L3 (dequeue)	O(1)	n	O(n)
L4/L5 (enqueue)	O(1)	n	O(n) ← dominates

Complexity

• Time: O(n).
• Space: O(w).

Useful when recursion depth is a concern; also the starting point for level-order problems.

Approach 3: Iterative DFS carrying depth

Stack of (node, current_depth) pairs.

def max_depth(root):
    if not root:
        return 0
    stack = [(root, 1)]   # L1: O(1) init with depth 1
    best = 0
    while stack:
        node, d = stack.pop()          # L2: O(1) pop
        best = max(best, d)            # L3: O(1) update best
        if node.left:
            stack.append((node.left, d + 1))   # L4: O(1) push
        if node.right:
            stack.append((node.right, d + 1))  # L5: O(1) push
    return best

Where the time goes, line by line

Variables: n = number of nodes in the tree, h = tree height, w = max tree width.

Line	Per-call cost	Times executed	Contribution
L2 (pop)	O(1)	n	O(n)
L3 (max)	O(1)	n	O(n)
L4/L5 (push)	O(1)	n	O(n) ← dominates (all lines tie)

Complexity

• Time: O(n).
• Space: O(h).

Summary

Approach	Time	Space
Recursive DFS	O(n)	O(h)
BFS level count	O(n)	O(w)
Iterative DFS with depth	O(n)	O(h)

All optimal; the one-line recursion is the canonical answer.

Test cases

from collections import deque

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

def build_tree(vals):
    if not vals: return None
    root = TreeNode(vals[0])
    q = [root]
    i = 1
    while q and i < len(vals):
        node = q.pop(0)
        if i < len(vals) and vals[i] is not None:
            node.left = TreeNode(vals[i])
            q.append(node.left)
        i += 1
        if i < len(vals) and vals[i] is not None:
            node.right = TreeNode(vals[i])
            q.append(node.right)
        i += 1
    return root

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

def _run_tests():
    assert max_depth(build_tree([3, 9, 20, None, None, 15, 7])) == 3
    assert max_depth(build_tree([1, None, 2])) == 2
    assert max_depth(None) == 0
    assert max_depth(build_tree([1])) == 1
    # skewed tree of depth 4
    t = TreeNode(1, TreeNode(2, TreeNode(3, TreeNode(4))))
    assert max_depth(t) == 4
    print("all tests pass")

if __name__ == "__main__":
    _run_tests()

Related data structures

• Binary Trees & BSTs, height computation
• Queues, BFS level count