Maximum Depth of Binary Tree

Find the number of nodes on the longest root-to-leaf path.

Start with the concrete trace below. It shows the state the algorithm must carry as it runs.

Problem trace

Maximum Depth of Binary Tree: Each recursive call returns the height of its subtree, so a parent needs only 1 + max(left height, right height).

Input and goalFind the number of nodes on the longest root-to-leaf path.

Start the root callFor tree [3,9,20,null,null,15,7], call max_depth(3). The stack contains [3], and neither child height is known yet.

• 3call max_depth(3)
  • 9
  • 20
    • 15
    • 7

callStack[3]knownReturnsnone

Recognize it

Use this pattern when a tree property for a node can be computed only after both child subtrees return summaries, especially height, diameter contributions, or root-to-leaf aggregates.

Keep true

Whenever max_depth(node) returns d, d is exactly the number of real nodes on the longest path from node to a leaf; max_depth(None) returns 0, making a leaf return 1.

Reuse it

Define the null identity first, ask each child for the smallest sufficient summary, and combine those summaries once; the same postorder fold supports subtree size, height, and path calculations.

Pattern: Bottom-up tree DFS.

Simple idea: A node’s depth is one plus the larger depth from its two children.

def max_depth(root: TreeNode | None) -> int:
   if root is None:
      return 0
   return 1 + max(max_depth(root.left), max_depth(root.right))

Cost: $O(n)$ time and $O(h)$ call-stack space, where $h$ is tree height.

The platform supplies TreeNode with val, left, and right; this snippet assumes that definition.