Given the root of a binary tree, return its maximum depth — the number of nodes along the longest path from the root down to the farthest leaf.

Examples

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

Common Approaches

Typical techniques for this pattern:

Approach Time Space Notes
Recursive DFS (this problem) O(n) O(h) stack Natural for trees and graphs
Iterative DFS (stack) O(n) O(n) Avoid recursion depth limits
DFS with memoization O(n) O(n) Overlapping subproblems on graphs
Backtracking DFS O(2^n) typical O(n) Enumerate choices with pruning

Thinking Process

Depth counts nodes, not edges. The tree is empty when root is null → depth 0.

Bottom-up DFS is the cleanest formulation:

  • Base case: null node → 0
  • Otherwise → 1 + max(left depth, right depth)

Each subtree returns its own height; the parent adds one for the current node. BFS level counting also works but needs a queue.

Tree DFS (bottom-up) 3 9 20 15 7 post-order: combine left + right + 1

Solution — O(n) time, O(h) space

class Solution {
public:
    int maxDepth(TreeNode* root) {
        if (!root) return 0;
        return 1 + max(maxDepth(root->left), maxDepth(root->right));
    }
};

Solution Explanation

Approach: Recursive DFS (this problem)

Key idea: Depth counts nodes, not edges. The tree is empty when root is null → depth 0.

How the code works: Bottom-up DFS is the cleanest formulation:

  • Base case: null node → 0
  • Otherwise → 1 + max(left depth, right depth)

Walkthrough — input root = [3,9,20,null,null,15,7], expected output 3:

  1. Initialize variables from the problem setup.
  2. Apply the main loop / recursion until the condition is met.
  3. Confirm the result matches the expected output.

Time: O(n) · Space: O(h)

Common Mistakes

  • Returning 1 for null instead of 0 (off-by-one on empty tree)
  • Counting edges instead of nodes
  • Top-down depth tracking with a running max — works but more error-prone than bottom-up

Key Takeaways

  • Post-order DFS (return 1 + max(left, right)) is the standard tree depth/height template
  • Depth from root (this problem) vs height from leaves — same recurrence, different framing
  • First of many tree DFS problems — master this before LCA, diameter, and path sums

References

Template Reference