Maximum Depth of Binary Tree

Problem

In distributed tracing systems, call trees represent nested service invocations where depth determines worst-case latency. Finding the maximum depth tells you the longest blocking call chain. Given the root of a binary tree, return the number of nodes along the longest path from the root to the farthest leaf.

    3
   / \
  9  20
    /  \
   15   7
→ 3
 
  1
   \
    2
→ 2

Solution

Approach - Postorder DFS recursion.

The depth of any node is 1 (for the node itself) plus the depth of its deeper child. That single sentence is the whole algorithm: recurse into root.left and root.right, take the larger of the two returned depths, and add 1. Because the parent's answer depends on both children's answers, the work happens after both recursive calls return - that is postorder. The base case is root is None, returning 0, because a missing node contributes no depth and gives the max a floor to build on.

Trace the tree 3 -> (9, 20 -> (15, 7)). The leaves 9, 15, and 7 each see two None children, so each returns 1 + max(0, 0) = 1. Node 20 takes 1 + max(1, 1) = 2 from its children 15 and 7. The root sees left_depth = 1 (from leaf 9) and right_depth = 2 (from node 20), returning 1 + max(1, 2) = 3. The answer flows upward, each node waiting on its subtrees before reporting its own depth. Using max rather than a sum is the key correctness point - depth tracks the single longest root-to-leaf path, not the total node count.

Edge cases - A None root returns 0 (empty tree). A single node returns 1. A degenerate one-sided chain returns its length, since the empty side contributes 0 and max picks the populated side.

Complexity - O(n) time, O(h) space - every node is visited once, and the call stack is as deep as the tree's height (O(log n) balanced, O(n) degenerate).