94. Maximum Depth of Binary Tree

The depth of a tree is one more than the deeper of its two subtrees. Recurse to the leaves (depth 0 for a missing child) and combine on the way back up.

Idea

Depth has a naturally recursive definition: the depth of a node's tree is 1 (for the node itself) plus the maximum depth of its two children. An empty subtree has depth 0. This bottoms out at the leaves and combines upward.

Algorithm

1. If root is None, return 0.
2. Otherwise return 1 + max(maxDepth(root.left), maxDepth(root.right)).

Each node is visited exactly once.

Worked example: [3,9,20,null,null,15,7]

      3
     / \
    9   20
       /  \
      15   7

• maxDepth(9) = 1 (leaf).
• maxDepth(15) = 1, maxDepth(7) = 1 → maxDepth(20) = 1 + max(1,1) = 2.
• maxDepth(3) = 1 + max(maxDepth(9)=1, maxDepth(20)=2) = 3.

Maximum depth = 3.

Complexity

• Time: O(n) — every node visited once.
• Space: O(h) recursion stack, where h is the tree height.

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