Maximum Depth of Binary Tree (LC 104)

Pattern: DFS - Bottom-Up (Post-Order)
Difficulty: Easy
Key Concept: Recursive “Bubble Up” — ask children for their height, add 1

Problem Statement

Find the longest path from the root node down to the farthest leaf node.

---

The Logic (Recursive Strategy)

At any node:

1. Ask the Left child: “What is your height?”
2. Ask the Right child: “What is your height?”
3. My height = 1 + max(Left Height, Right Height)
4. Base Case: If I am null, my height is 0

---

Java Implementation

class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) return 0;

        int leftHeight = maxDepth(root.left);
        int rightHeight = maxDepth(root.right);

        return 1 + Math.max(leftHeight, rightHeight);
    }
}

---

Dry Run

Tree:
      3
     / \
    9   20
       /  \
      15   7

Step-by-Step:

1. maxDepth(3) calls maxDepth(9) and maxDepth(20)

2. maxDepth(9):

   • Left = null → returns 0
   • Right = null → returns 0
   • Result: 1 + max(0, 0) = 1

3. maxDepth(20):

   • maxDepth(15) → returns 1 (both children null)
   • maxDepth(7) → returns 1 (both children null)
   • Result: 1 + max(1, 1) = 2

4. Back at maxDepth(3):

   • leftHeight = 1 (from node 9)
   • rightHeight = 2 (from node 20)
   • Final Result: 1 + max(1, 2) = 3

---

Call Stack Visualization

maxDepth(3)
 ├── maxDepth(9) → returns 1
 └── maxDepth(20)
      ├── maxDepth(15) → returns 1
      └── maxDepth(7)  → returns 1
     (20 returns 1 + max(1,1) = 2)
(3 returns 1 + max(1,2) = 3)

---

Pattern Recognition

• Pattern: Bottom-Up DFS
• Why? You cannot know the answer for the current node until you know the answers from its children
• Reuse this template for: Height, Diameter, Balanced Tree, Longest Path → always 1 + Math.max(left, right)

---

Complexity

Metric	Value	Explanation
Time	O(n)	Visit every node once
Space	O(h)	h = height (recursion stack depth)