Maximum Depth of Binary Tree

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, 10^4].
• -100 <= Node.val <= 100

Approach: Recursion (Optimal Solution)

Algorithm

1. Base case: if the current node is null, its depth is 0
2. Recursively compute the maximum depth of the left subtree and the right subtree
3. Return 1 + max(leftDepth, rightDepth) — the current node counts as one level

Key Insight

The maximum depth of a tree is defined recursively: the depth of a node is 1 plus the deeper of its two subtrees. This is a textbook top-down (or post-order) recursion where each node is visited exactly once.

Time & Space Complexity

• Time Complexity: O(n) - every node is visited once
• Space Complexity: O(n) - recursion stack in the worst case (a skewed tree)

Java Implementation

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class MaximumDepthOfBinaryTree {

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

Example Walkthrough

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

1. maxDepth(9) = 1 + max(0, 0) = 1
2. maxDepth(15) = 1 + max(0, 0) = 1
3. maxDepth(7) = 1 + max(0, 0) = 1
4. maxDepth(20) = 1 + max(1, 1) = 2
5. maxDepth(3) = 1 + max(1, 2) = 3

Alternative Approach: Iterative BFS

import java.util.ArrayDeque;
import java.util.Deque;

public class MaximumDepthBFS {

    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        Deque<TreeNode> queue = new ArrayDeque<>();
        queue.offer(root);
        int depth = 0;
        while (!queue.isEmpty()) {
            depth++;
            for (int i = queue.size(); i > 0; i--) {
                TreeNode node = queue.poll();
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
        }
        return depth;
    }
}

The BFS variant counts levels level by level, using O(n) extra space for the queue. The recursive DFS approach is simpler and equally efficient in time.

Key Insights

1. Post-order Pattern: The depth is known only after both subtrees are computed
2. Null Base Case: Returning 0 for null naturally handles empty and leaf nodes
3. Skewed Tree Worst Case: For a chain of n nodes, the recursion stack grows to O(n)
4. Balance Not Required: The formula works for any binary tree shape

The recursive solution is the optimal approach, providing O(n) time and O(n) space.