5.4 Maximum Depth of Binary Tree

5.4.1 Problem Metadata

5.4.2 Description

Return the maximum depth (number of nodes along the longest path from root down to a leaf).

5.4.3 Examples

Example 1: Balanced Tree

Input:
    3
   / \
  9  20
    /  \
   15   7
Output: 3
Explanation: Longest path is 3 → 20 → 15 (or 3 → 20 → 7), which has 3 nodes

Example 2: Single Node

Input: 1
Output: 1

Example 3: Skewed Tree

Input:
  1
   \
    2
     \
      3
Output: 3
Explanation: Linear right spine, depth equals number of nodes

5.4.4 Constraints

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

5.4.5 Solution - DFS Recursion

5.4.5.1 Walkthrough

The maximum depth is the longest path from root to any leaf node. Use a recursive DFS approach:

  1. Base case: If current node is null, return 0 (no depth).
  2. Recursive case: The depth of the current node is 1 (for the node itself) plus the maximum of the depths of its left and right subtrees.
  3. This naturally explores all paths and returns the longest one.

The elegance of this approach is that max(left_depth, right_depth) inherently finds the longest path at each level as it bubbles up the recursion stack.

5.4.5.2 Analysis

  • Time Complexity: O(n) — each node is visited exactly once
  • Space Complexity: O(h) — recursion stack depth, where h is tree height (O(n) in worst case for skewed tree)

5.4.5.3 Implementation Steps

  1. Handle null node as base case returning 0
  2. Recursively calculate depth of left subtree
  3. Recursively calculate depth of right subtree
  4. Return 1 + max(left_depth, right_depth)

5.4.5.4 Code - Java

public int maxDepth(TreeNode root) {
    if (root == null) {
        return 0;
    }
    return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}