LeetCode 104: Maximum Depth of Binary Tree Solution in Python Explained

Problem Statement

In LeetCode 104, you’re given the root of a binary tree. Your task is to return its maximum depth, defined as the number of nodes from the root to the farthest leaf, including both ends. This contrasts with zigzag traversal like LeetCode 103: Binary Tree Zigzag Level Order Traversal, focusing on depth rather than level-wise ordering.

Constraints

• Number of nodes: 0 <= n <= 10^4
• Node values: -100 <= Node.val <= 100

Example

Let’s see some cases:

Copy codeInput: root = [3,9,20,null,null,15,7]
      3
     / \
    9  20
       / \
      15  7
Output: 3
Explanation: Longest path (3->20->15 or 3->20->7) has 3 nodes.

Copy codeInput: root = [1,null,2]
      1
       \
        2
Output: 2
Explanation: Path 1->2 has 2 nodes.

Copy codeInput: root = []
Output: 0
Explanation: Empty tree has depth 0.

These examples show we’re finding the longest root-to-leaf path.

Understanding the Problem

How do you solve LeetCode 104: Maximum Depth of Binary Tree in Python? Take root = [3,9,20,null,null,15,7]. We need the maximum depth—paths 3->20->15 and 3->20->7 both have 3 nodes, so return 3. For [1,null,2], depth is 2. This isn’t a symmetry check like LeetCode 101: Symmetric Tree; it’s about measuring tree height. We’ll use: 1. Recursive DFS: O(n) time, O(h) space—our best solution. 2. Queue-Based BFS: O(n) time, O(w) space—an alternative.

Let’s dive into the best solution.

Best Solution: Recursive DFS Approach

Explanation

Recursive DFS calculates the maximum depth by recursively computing the depth of each subtree—returning 0 for null nodes and 1 plus the maximum of left and right depths for non-null nodes. It’s the best solution due to its simplicity, efficiency, and natural fit for tree depth calculation, leveraging recursion to explore all paths.

For [3,9,20,null,null,15,7]:

• Depth of 3 = 1 + max(depth(9), depth(20)).
• Depth of 9 = 1, depth of 20 = 1 + max(depth(15), depth(7)) = 2.
• Total = 1 + 2 = 3.

Step-by-Step Example

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

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

Goal: Return 3.

• Start: Call maxDepth(3).
• Step 1: root = 3.
• Left: maxDepth(9).
• 9 has no children, return 1.
• Right: maxDepth(20).
• Left: maxDepth(15) → 1.
• Right: maxDepth(7) → 1.
• 20 depth = 1 + max(1, 1) = 2.
• 3 depth = 1 + max(1, 2) = 3.
• Finish: Return 3.

Example 2: root = [1,null,2]

Goal: Return 2.

• Start: maxDepth(1).
• Step 1: root = 1.
• Left: maxDepth(None) → 0.
• Right: maxDepth(2).
• 2 has no children, return 1.
• 1 depth = 1 + max(0, 1) = 2.
• Finish: Return 2.

Example 3: root = []

Goal: Return 0.

• Start: maxDepth(None).
• Step 1: Null root, return 0.
• Finish: Return 0.

How the Code Works (Recursive DFS) – Detailed Line-by-Line Explanation

Here’s the Python code with a thorough breakdown:

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

def maxDepth(root: TreeNode) -> int:
    # Line 1: Base case - check if root is null
    if not root:
        # If root is None (e.g., empty tree or leaf’s child), depth is 0
        return 0

    # Line 2: Calculate left subtree depth
    left_depth = maxDepth(root.left)
    # Recursively gets depth of left child (e.g., 9 → 1)
    # Explores left subtree fully

    # Line 3: Calculate right subtree depth
    right_depth = maxDepth(root.right)
    # Recursively gets depth of right child (e.g., 20 → 2)
    # Explores right subtree fully

    # Line 4: Return maximum depth including current node
    return 1 + max(left_depth, right_depth)
    # Adds 1 for current node, takes max of subtrees
    # e.g., root=3, left=1, right=2 → 1 + max(1, 2) = 3

This detailed breakdown clarifies how recursive DFS efficiently computes the maximum depth.

Alternative: Queue-Based BFS Approach

Explanation

Queue-Based BFS processes the tree level-by-level, counting levels as it goes. Enqueue nodes with their depth, incrementing depth for each new level. It’s a practical alternative, using breadth-first traversal to measure height explicitly.

For [3,9,20,null,null,15,7]:

• Level 1: [3].
• Level 2: [9,20].
• Level 3: [15,7].
• Max depth = 3.

Step-by-Step Example (Alternative)

For [3,9,20,null,null,15,7]:

• Start: queue = [(3, 1)], max_depth = 0.
• Step 1: Pop (3,1), max_depth = 1, add (9,2), (20,2).
• Step 2: Pop (9,2), max_depth = 2, no children.
• Step 3: Pop (20,2), max_depth = 2, add (15,3), (7,3).
• Step 4: Pop (15,3), max_depth = 3, no children.
• Step 5: Pop (7,3), max_depth = 3, no children.
• Finish: Return 3.

How the Code Works (BFS)

Copy codefrom collections import deque

def maxDepthBFS(root: TreeNode) -> int:
    if not root:
        return 0
    queue = deque([(root, 1)])
    max_depth = 0
    while queue:
        node, depth = queue.popleft()
        max_depth = max(max_depth, depth)
        if node.left:
            queue.append((node.left, depth + 1))
        if node.right:
            queue.append((node.right, depth + 1))
    return max_depth

Complexity

• Recursive DFS:
• Time: O(n) – visits each node once.
• Space: O(h) – recursion stack, h = height.
• Queue-Based BFS:
• Time: O(n) – visits each node once.
• Space: O(w) – queue size, w = max width.

Efficiency Notes

Recursive DFS is the best solution with O(n) time and O(h) space, offering a concise, efficient approach—Queue-Based BFS matches time complexity with O(w) space, providing a level-wise alternative that’s intuitive for breadth-first exploration.

Key Insights

• Depth: Longest root-to-leaf path.
• DFS: Recursive height calculation.
• BFS: Level counting.

Additional Example

For root = [1,2,3,4,null,null,5]:

• Goal: 3.
• DFS: Depth of 1 = 1 + max(2’s depth=2, 3’s depth=1) = 3.

Edge Cases

• Empty Tree: [] → 0.
• Single Node: [1] → 1.
• Skewed Tree: [1,2,3] → 3.

Both solutions handle these well.

Final Thoughts

LeetCode 104: Maximum Depth of Binary Tree in Python is a fundamental tree challenge. The Recursive DFS solution stands out for its efficiency and simplicity, while Queue-Based BFS offers a breadth-first perspective. Want more? Try LeetCode 102: Binary Tree Level Order Traversal for level-wise traversal or LeetCode 94: Binary Tree Inorder Traversal for inorder basics. Ready to practice? Solve LeetCode 104 on LeetCode with [3,9,20,null,null,15,7], aiming for 3—test your skills now!