104 - Maximum Depth of Binary Tree

Difficulty: Easy | Pattern: Tree DFS / BFS | Company tags: Amazon, Google, Facebook, LinkedIn

Problem Statement

Given the root of a binary tree, return its maximum depth.

A binary tree's maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

Example 1:

    3
   / \
  9  20
     / \
    15   7

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

Example 2:

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

Algorithm Flow

Approach 1: Recursive DFS

Key insight: The depth of a tree is 1 (for the root) + the maximum depth of its left and right subtrees.

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

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

Trace on Example 1:

• maxDepth(3) = 1 + max(maxDepth(9), maxDepth(20))
• maxDepth(9) = 1 + max(0, 0) = 1
• maxDepth(20) = 1 + max(maxDepth(15), maxDepth(7)) = 1 + max(1, 1) = 2
• maxDepth(3) = 1 + max(1, 2) = 3 ✓

Approach 2: Iterative BFS (Level Order)

Count the number of levels by doing a BFS. Each level processed = depth increases by 1.

from collections import deque

def maxDepth(root) -> int:
    if not root:
        return 0
    queue = deque([root])
    depth = 0
    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

Approach 3: Iterative DFS (Stack)

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

Edge Cases

• Empty tree (root = null) → 0
• Single node → 1
• All nodes on one side (skewed tree) → depth = n

Complexity

Approach	Time	Space
Recursive DFS	O(n)	O(h) where h = tree height (O(n) worst case skewed)
Iterative BFS	O(n)	O(w) where w = max width
Iterative DFS	O(n)	O(h)

Key Terms

Term	Definition
Recursion	Computing depth by recursively combining 1 + max(left depth, right depth) from the base case up.
Tree height/depth	The number of nodes (or edges, depending on convention) on the longest root-to-leaf path.
DFS (Depth-First Search)	Traversal going as deep as possible before backtracking; natural fit for a recursive or stack-based depth calculation.
BFS (Breadth-First Search)	Level-by-level traversal using a queue; depth equals the number of levels processed.

FAQ

Q: Can this be solved without extra space? A: No traversal-based tree algorithm can avoid O(h) or O(w) auxiliary space (call stack or queue) unless the tree is threaded; that overhead is inherent to the problem.

Q: What if the tree is empty (root is null)? A: All three approaches return 0 immediately via the if not root: return 0 guard.

Q: What's the difference between the iterative BFS and iterative DFS approaches here? A: BFS counts full levels (depth += 1 once per level using the level_size snapshot trick), while DFS tracks depth per node explicitly on the stack and takes the max seen.

Q: How would this change for Minimum Depth of Binary Tree (LC 111)? A: You'd take the minimum instead of the maximum, but must special-case nodes with only one child — a single-child node isn't a "shortest path" leaf, so you can't just take min naively.

Q: Recursive vs iterative — which is preferred in an interview? A: The recursive one-liner is expected first for clarity; mention the iterative versions if asked about stack overflow risk on very deep/skewed trees (Python's default recursion limit is ~1000).

Quick Revision

• Depth of a tree = 1 + max(depth of left subtree, depth of right subtree).
• Base case: None node has depth 0.
• Recursive DFS is the cleanest solution — a two-line function.
• Iterative BFS counts levels by processing the queue level by level (same level_size trick as level-order traversal).
• Iterative DFS uses an explicit stack storing (node, depth) pairs and tracks the running max.
• Time is O(n) for all three approaches — every node visited once.
• Space differs: O(h) for DFS (recursion stack/explicit stack), O(w) for BFS (queue).
• Skewed tree gives worst-case O(n) space for DFS since h = n.

Related Problems

• 100 - Same Tree — same recursive tree DFS pattern comparing subtree results.
• 102 - Binary Tree Level Order Traversal — same BFS/queue level-counting pattern used in the iterative BFS approach here.
• Minimum Depth of Binary Tree (pattern: same recursive depth calculation, but takes min with a leaf special case) — LeetCode 111, not in this directory.
• Balanced Binary Tree (pattern: reuses depth calculation to check height difference at every node) — LeetCode 110, not in this directory.