← ~/lc-grind/posts

#104 - Maximum Depth of Binary Tree

July 14, 2025

Maximum Depth of Binary Tree

Problem Description

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:


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

Example 2:


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

Constraints:

  • The number of nodes in the tree is in the range [0, 104].
  • -100 <= Node.val <= 100

Solution

1. Problem Deconstruction

Technical Definition

Given the root node ( r ) of a binary tree ( T ), compute the maximum depth ( D(T) ), defined as the maximum count of nodes encountered along any root-to-leaf path. A leaf node has no children. Formally:

  • ( D(T) = 0 ) if ( r = \text{null} ) (empty tree).
  • ( D(T) = 1 ) if ( r ) has no children (single-node tree).
  • ( D(T) = 1 + \max(D(T_{\text{left}}), D(T_{\text{right}})) ) where ( T_{\text{left}} ) and ( T_{\text{right}} ) are left/right subtrees.

Beginner Explanation

Imagine a family tree where each person has at most two children. Starting from the top ancestor, find the longest chain of parent-child links ending at someone with no children. Count every person (including the top ancestor) in that chain.

Mathematical Formulation

Let ( h(n) ) = depth of subtree rooted at node ( n ):

h(n)={0if n=null1+max⁡(h(n.left),h(n.right))otherwiseh(n) = \begin{cases} 0 & \text{if } n = \text{null} \\ 1 + \max(h(n.\text{left}), h(n.\text{right})) & \text{otherwise} \end{cases}

Return ( h(\text{root}) ).

Constraint Analysis

  • Nodes in [0, 10⁴]:
    • Limitation: Recursive solutions may hit stack limits (10⁴-depth skewed trees). Requires iterative or tail-recursive approaches.
    • Edge Case: Empty tree (( \text{root} = \text{null} )) → depth = 0.
  • Node values [-100, 100]:
    • Irrelevance: Values don’t affect depth; only tree structure matters.

2. Intuition Scaffolding

Analogies

  1. Real-World (Mining Expedition): Digging a mine with branches. Longest path from entrance to deepest dead-end (no further tunnels). Each junction counts as a node.
  2. Gaming (RPG Skill Tree): Longest chain of upgrades from the base skill, where each skill requires the previous one.
  3. Math (Recursive Sequence): Depth = 1 + max(left subsequence length, right subsequence length).

Common Pitfalls

  1. Edge vs. Node Counting: Depth = nodes (not edges). Pitfall: Returning 0 for root instead of 1.
  2. Skewed Tree Ignorance: Assuming balanced trees; recursion depth ( \sim 10^4 ) may crash.
  3. Partial Null Handling: Only checking one child’s existence (e.g., missing if node.left).
  4. BFS Level Miscount: Forgetting to increment depth after processing a level.
  5. DFS Stack Corruption: Pushing right child before left (LIFO order matters for DFS).

3. Approach Encyclopedia

1. Recursive DFS (Postorder)

Pseudocode:

def maxDepth(root):  
    if root is null: return 0  
    left_depth = maxDepth(root.left)  
    right_depth = maxDepth(root.right)  
    return 1 + max(left_depth, right_depth)

Complexity Proof:

  • Time: ( O(n) ) — Each node visited once. Derivation: ( T(n) = 2T(n/2) + O(1) ) → Master Theorem Case 1 → ( O(n) ).
  • Space: Worst-case ( O(n) ) (skewed tree), best ( O(\log n) ) (balanced).
    Visualization:
    3        Depth: 1 + max( 
   / \           h(9)=1, 
  9   20         h(20)=1 + max(h(15)=1, h(7)=1) = 2 
      / \    → Output: 1 + max(1,2) = 3 
     15  7

2. Iterative BFS (Level Order)

Pseudocode:

def maxDepth(root):  
    if not root: return 0  
    queue = [root]  
    depth = 0  
    while queue:  
        depth += 1  
        level_size = len(queue)  
        for i in range(level_size):  
            node = queue.pop(0)  
            if node.left: queue.append(node.left)  
            if node.right: queue.append(node.right)  
    return depth

Complexity Proof:

  • Time: ( O(n) ) — Each node enqueued/dequeued once.
  • Space: ( O(n) ) — Worst-case queue holds all leaves (( \sim n/2 ) nodes).
    Visualization:
Level 0: [3] → depth=1  
Level 1: [9, 20] → depth=2  
Level 2: [15, 7] → depth=3

3. Iterative DFS (Preorder)

Pseudocode:

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

Complexity Proof:

  • Time: ( O(n) ) — Each node pushed/popped once.
  • Space: ( O(n) ) — Worst-case stack holds all nodes.
    Visualization:
Stack: [(3,1)] → pop → max_depth=1  
Push: (20,2), (9,2) → pop (9,2) → max_depth=2  
Pop (20,2) → push (7,3), (15,3) → pop (15,3) → max_depth=3

4. Code Deep Dive

Optimal Solution (Iterative BFS)

from collections import deque  

class Solution:  
    def maxDepth(self, root: Optional[TreeNode]) -> int:  
        if not root:  # Edge: Empty tree  
            return 0  
        queue = deque([root])  # Initialize queue with root  
        depth = 0  # Depth counter  
        while queue:  
            depth += 1  # Enter new level  
            level_size = len(queue)  # Fix current level size  
            for _ in range(level_size):  # Process entire level  
                node = queue.popleft()  # FIFO extraction  
                if node.left:  
                    queue.append(node.left)  # Enqueue left child  
                if node.right:  
                    queue.append(node.right)  # Enqueue right child  
        return depth  # Total levels = depth

Line-by-Line Annotation

  1. if not root: return 0: Handles empty tree (constraint-derived edge case).
  2. queue = deque([root]): Efficient FIFO using deque (O(1) popleft).
  3. depth = 0: Initialize counter.
  4. while queue:: Continue until all nodes processed.
  5. depth += 1: Each loop iteration = one new level.
  6. level_size = len(queue): Snapshot of current level’s nodes.
  7. for _ in range(level_size): Exhaust entire level before moving deeper.
  8. node = queue.popleft(): Process nodes in insertion order (BFS).
  9. if node.left: queue.append(node.left): Push left child if exists.
  10. if node.right: queue.append(node.right): Push right child if exists.

Edge Case Handling

  • Example 1 (Balanced):
    • Level 0: [3] → depth=1 → push [9,20]
    • Level 1: [9,20] → depth=2 → push [15,7]
    • Level 2: [15,7] → depth=3 → return.
  • Example 2 (Skewed):
    • Level 0: [1] → depth=1 → push [2]
    • Level 1: [2] → depth=2 → no children → return.

5. Complexity War Room

Hardware-Aware Analysis

  • 10⁴ Nodes:
    • Time: ( O(10^4) ) → ~0.1 ms (modern CPU).
    • Space: Queue holds ( \sim 5000 ) nodes (worst-case last level) → ~40 KB (8 bytes/node). Fits in L2/L3 cache.

Industry Comparison Table

Approach Time Space Readability Interview Viability
Recursive DFS O(n) O(n) 10/10 ❌ Fails for 10⁴ depth
Iterative BFS O(n) O(n) 9/10 ✅ Robust
Iterative DFS O(n) O(n) 8/10 ✅ Explainable

6. Pro Mode Extras

Variants

  1. Minimum Depth (Leetcode 111):
    def minDepth(root):  
    if not root: return 0  
    if not root.left and not root.right: return 1  # Leaf  
    if not root.left: return 1 + minDepth(root.right)  # Only right  
    if not root.right: return 1 + minDepth(root.left)  # Only left  
    return 1 + min(minDepth(root.left), minDepth(root.right))
  2. Balanced Check (Leetcode 110):
    def isBalanced(root):  
    def check(node):  
        if not node: return 0  
        left = check(node.left)  
        right = check(node.right)  
        if left == -1 or right == -1 or abs(left - right) > 1:  
            return -1  
        return 1 + max(left, right)  
    return check(root) != -1

Interview Cheat Sheet

  • First Response: “Depth = nodes in longest root-leaf path. Constraints: 0-10⁴ nodes → avoid recursion.”
  • Key Insight: “BFS levels = depth. DFS needs explicit depth tracking.”
  • Corner Cases: “Empty tree, single node, skewed trees.”
  • Complexity: “Always state time/space first: O(n) for both.”