LeetCode Link: 104. Maximum Depth of Binary Tree

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:

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

Understanding the Problem

Before diving into the solution, let's clarify two important concepts:

  1. Depth: The distance from the root to a given node
  2. Height: The distance from a given node to the deepest leaf

Interestingly, the maximum depth of a binary tree is the same as the height of the root node. This means we can approach this problem from two different angles:

Solution Approaches

1. Recursive Approach (DFS)

There are two ways to implement the recursive approach:

Approach 1: Bottom-up (Post-order Traversal)

This is the most intuitive approach. We calculate the height of the tree by:

  1. Recursively finding the height of the left subtree
  2. Recursively finding the height of the right subtree
  3. Taking the maximum of these two heights and adding 1 (for the current node)
class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        # Base case: If the node is None, height is 0
        if not root:
            return 0
        
        # Recursively calculate the height of left and right subtrees
        left_height = self.maxDepth(root.left)    # Left
        right_height = self.maxDepth(root.right)  # Right
        
        # Return the maximum height + 1 (for the current node)
        return 1 + max(left_height, right_height) # Middle
python

This solution uses the post-order traversal (left → right → middle) pattern, which is particularly well-suited for solving tree height problems.

Approach 2: Top-down (Pre-order Traversal)

We can also solve this using a pre-order traversal approach:

class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        # Initialize result
        self.result = 0
        
        def getDepth(node, depth):
            if not node:
                return
            
            # Update result if current depth is greater
            self.result = max(self.result, depth)  # Middle
            
            # Recursively check left and right subtrees
            getDepth(node.left, depth + 1)         # Left
            getDepth(node.right, depth + 1)        # Right
        
        if not root:
            return 0
            
        getDepth(root, 1)
        return self.result
python

This approach clearly shows the backtracking process when calculating depth. We pass the current depth to each recursive call and update our global result variable when we find a deeper path.

2. Iterative Approach (BFS - Level Order Traversal)

Since the maximum depth equals the number of levels in the tree, we can use level-order traversal:

from collections import deque

class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        if not root:
            return 0
        
        depth = 0
        queue = deque([root])
        
        while queue:
            # Process all nodes at the current level
            size = len(queue)
            depth += 1  # Increment depth for each level
            
            for _ in range(size):
                node = queue.popleft()
                
                # Add children to the queue
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
        
        return depth
python

This approach is very intuitive: we simply count the number of levels we process during the traversal.

Time and Space Complexity Analysis

Recursive Approaches:

  • Time Complexity: O(n) where n is the number of nodes in the tree
  • Space Complexity: O(h) where h is the height of the tree (due to the recursion stack)
    • In the worst case of a skewed tree, this becomes O(n)
    • In the best case of a balanced tree, this becomes O(log n)

Iterative Approach:

  • Time Complexity: O(n) where n is the number of nodes in the tree
  • Space Complexity: O(w) where w is the maximum width of the tree
    • In the worst case, this could be O(n/2) ≈ O(n) for a complete binary tree
    • In the best case, this becomes O(1) for a skewed tree