Given the root of a binary tree, return its maximum depth (the number of nodes on the longest root-to-leaf path).

Example 1:

• Input: root = [3,9,20,null,null,15,7]
• Output: 3

Example 2:

• Input: root = [1,null,2]
• Output: 2

Constraints:

• 0 ≤ tree nodes ≤ 10⁴

The foundational tree problem introducing tree traversal and recursive thinking.

Pattern: Tree Recursion

Solve for the left subtree, solve for the right subtree, then combine the results.

graph TD
    Root["TreeNode (Root)"] -->|Recurse Left| Left["Left Subtree"]
    Root -->|Recurse Right| Right["Right Subtree"]
    Left --> Base1{"Base Case (null)"}
    Right --> Base2{"Base Case (null)"}
    Base1 --> Combine["Combine Results"]
    Base2 --> Combine
    Combine --> Ans["Return Root Value / Depth"]

// Recursive DFS is standard

• Time Complexity: O(n)
• Space Complexity: O(h)
• Explanation: DFS recursion.

function maxDepth(root) {
  if (!root) return 0;
  return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}

• Time Complexity: O(n)
• Space Complexity: O(h)
• Explanation: Recursive DFS.

1. Initialize State: Setup necessary pointers, dynamic programming arrays, or hash maps.
2. Iterate & Evaluate: Process the input according to the boundary conditions.
3. Update & Return: Compute the optimal answer and return early or at termination.

1. Base case: empty tree depth 0
2. Node depth = 1 + max(left, right)
3. Classic divide-and-conquer on trees

1. Depth of empty tree is 0.
2. Depth of a node = 1 + max(depth of left, depth of right).
3. Use recursion.

👉 Solve this problem interactively in the DSA Lab