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.

Examples

Example 1

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

Tree:
      3
     / \
    9  20
      /  \
     15   7

Depth: Root (3) has depth 1, nodes (9, 20) have depth 2,
       nodes (15, 7) have depth 3

Example 2

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

Tree:
    1
     \
      2

Example 3

Input: root = []
Output: 0

Intuition

The depth of a tree is determined by its tallest subtree + 1 (for the root).

Think recursively:

• Depth of null node = 0
• Depth of any node = 1 + max(depth of left subtree, depth of right subtree)

This naturally fits a post-order DFS traversal where we calculate subtree depths before using them.

Pattern Recognition

This is a Tree Recursion problem with:

• Post-order traversal (process children before parent)
• Simple recursive definition
• Bottom-up calculation

Approach

Recursive DFS (Recommended)

1. Base Case: If node is null, return 0
2. Recursive Case:
   • Calculate left subtree depth
   • Calculate right subtree depth
   • Return 1 + max(left_depth, right_depth)

Why this works:

• Each node's depth = 1 (itself) + maximum depth of its subtrees
• Recursion naturally handles all branches
• Base case handles leaf nodes correctly

Iterative BFS (Alternative)

Use level-order traversal:

1. Use a queue, start with root
2. Count the number of levels processed
3. Each complete level increments depth

Edge Cases

• Empty tree (null root) → return 0
• Single node → return 1
• Skewed tree (only left or only right children)
• Balanced tree

Complexity Analysis

• Time: O(n) where n = number of nodes

  • Visit each node exactly once
  • O(1) work per node

• Space: O(h) where h = height of tree

  • Recursion call stack
  • O(log n) for balanced tree, O(n) for skewed tree