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.

Additional information

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

Example 1:

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

Example 2:

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

Example 3:

Input: root = []
Output: 0

Depth-First Search (Recursive)

Intuition
The depth of a tree is 1 (for the current node) plus the maximum depth of its children. Since this definition is recursive, we can write a simple DFS function.
If a node is empty, its depth is 0. Otherwise, we calculate the max depth of the left subtree and the right subtree, pick the larger one, and add 1.

Algorithm

1. Base Case: If root is None, return 0.
2. Recurse: Calculate max_depth(root.left) and max_depth(root.right).
3. Return: Return 1 + max(left_depth, right_depth).

def max_depth(root: Optional[TreeNode]) -> int:
    if not root:
        return 0
    
    return 1 + max(max_depth(root.left), max_depth(root.right))

Time & Space Complexity

• Time complexity: O(n)

• Reason: We traverse every node exactly once.

• Space complexity: O(h)

• Reason: The recursion stack depends on the height of the tree h. In the worst case (skewed tree), this is O(n). In the best case (balanced tree), this is O(log n).

Breadth-First Search (Iterative)

Intuition
We can use a Level Order Traversal (BFS) to count the depth. We process the tree layer by layer. For every level we fully process, we increment our depth counter.

Algorithm

1. If root is None, return 0.
2. Initialize a deque with the root.
3. Initialize level = 0.
4. While the queue is not empty:

• Snapshot the length of the queue (this is the number of nodes in the current level).
• Loop that many times to pop nodes and add their children.
• Increment level after processing the whole batch.

5. Return level.

from collections import deque

def max_depth(root: Optional[TreeNode]) -> int:
    if not root:
        return 0
        
    queue = deque([root])
    level = 0
    
    while queue:
        # Process all nodes at the current level
        for i in range(len(queue)):
            node = queue.popleft()
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        
        level += 1
        
    return level

Time & Space Complexity

• Time complexity: O(n)

• Reason: We visit every node once.

• Space complexity: O(n)

• Reason: In the worst case (a full binary tree), the queue holds the entire bottom level, which is roughly n/2 nodes.