104. Maximum Depth of Binary Tree

# Question

Given the root of a binary tree, return its maximum depth. The maximum depth is defined as the number of nodes along the longest path from the root node down to the farthest leaf node.

# Solution

# Pattern

Recursive Divide and Conquer (DFS) Break the problem down by computing the solution for the left and right subtrees independently, then combining them with the current root.

# How to Identify

• The problem asks for properties of a tree that depend on sub-results (e.g., max depth, min depth, path sum, balanced status).
• The solution naturally flows from bottom-up or top-down recursive traversal.
• The tree structure allows recursive sub-problems.

# Description

Step-by-step explanation:

1. Base Case: If the current node (root) is null, it contributes 0 to the depth. Return 0.
2. Left Subtree Recursion: Recursively call maxDepth(root.left) to find the maximum depth of the left branch.
3. Right Subtree Recursion: Recursively call maxDepth(root.right) to find the maximum depth of the right branch.
4. Combine: Take the maximum value between the left and right subtree depths, add 1 to account for the current node itself, and return it up the call stack.

# The Intuition

Think of this like measuring the height of a multi-story building from the roof down to the foundation. You ask the left wing of the building how tall it is, and you ask the right wing how tall it is. Whichever wing is taller dictates the height of your current floor, and you add 1 for your own floor before reporting that total up to the floor above you.

# Complexity

# Time Complexity

$O(N)$, where $N$ is the total number of nodes in the binary tree. Every single node is visited exactly once during the traversal.

# Space Complexity

• Worst Case ($O(N)$): Occurs when the binary tree is completely skewed (like a linked list), causing the system call stack to grow linearly with the number of nodes.
• Average Case ($O(\log N)$): Occurs when the binary tree is balanced, meaning the maximum height of the call stack is proportional to the tree's height.

# Code

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

# Caveats

• Stack Overflow Risk: In languages or environments with restricted call stack sizes, a heavily skewed tree with $N = 10^5$ nodes can cause a StackOverflowError in recursive DFS. In such extreme production scenarios, an iterative Breadth-First Search (BFS) level-order traversal using a Queue should be preferred.

# Concepts to Think About

• Post-order Traversal Nature: This recursive pattern executes a post-order traversal because we must evaluate both child subtrees before we can compute the result for the parent node.
• State Propagation: Notice how state flows upwards from the leaves to the root in this problem, unlike top-down traversals where you pass a running path sum downward.

# Logical Follow-up

Question: How would you modify this approach to find the Minimum Depth of a binary tree (the shortest path from root down to the nearest leaf)? Solution: While maximum depth simply takes 1 + Math.max(...), minimum depth requires care. If a node has only one child, the missing child returns 0, which would erroneously make Math.min choose 0. You must add explicit conditional checks: if root.left == null, return 1 + maxDepth(root.right); if root.right == null, return 1 + maxDepth(root.left). Otherwise, return 1 + Math.min(leftDepth, rightDepth).