DSAMotivator

Maximum Depth of Binary Tree

Easy·🌳 Trees & BST·Open on LeetCode ↗

Return the number of nodes along the longest path from the root down to any leaf.

root = [3, 9, 20, null, null, 15, 7]step 1/12
3920157

Depth of a tree is one more than the depth of its deeper subtree.

1def max_depth(root):
2    if root is None:
3        return 0
4    return 1 + max(max_depth(root.left), max_depth(root.right))
Read the 12 steps as text
  1. 1Depth of a tree is one more than the depth of its deeper subtree.
  2. 2Descend into 3.
  3. 3Descend into 9.
  4. 49 is a leaf, so its subtree is 1 deep.
  5. 5Descend into 20.
  6. 6Descend into 15.
  7. 715 is a leaf, so its subtree is 1 deep.
  8. 8Descend into 7.
  9. 97 is a leaf, so its subtree is 1 deep.
  10. 10Below 20: 1 on one side, 1 on the other. Its depth is 1 + 1 = 2.
  11. 11Below 3: 1 on one side, 2 on the other. Its depth is 1 + 2 = 3.
  12. 12The longest root-to-leaf path is 3 nodes.

The idea

The depth of a tree is one more than the depth of its deeper subtree. That sentence is both the definition and the code — which is what makes this the problem people use to explain tree recursion.

The base case is where the real understanding sits. An empty tree has depth 0, not 1. Anchoring on null rather than on leaves means you never have to write a special case for a node with one child.

It's worth noticing the shape of the recursion: the answer flows *upward*. Each call hands its parent a single number, and the parent combines its two numbers into one. Nothing is passed down. That's the post-order shape, and a large fraction of tree problems are variations on it.

The approach

  1. 1If the node is null, the depth is 0.
  2. 2Otherwise recurse into both children.
  3. 3Return 1 plus the larger of the two results — the 1 accounts for the current node.

Complexity

Time
O(n)
Space
O(h)

Every node is visited once. The space is the recursion stack, which is the height — O(log n) balanced, O(n) for a tree degenerated into a list.

Code

def max_depth(root):
    if root is None:
        return 0
    return 1 + max(max_depth(root.left), max_depth(root.right))

What goes wrong

  • •Basing the recursion on leaves instead of null, which forces awkward handling of nodes with exactly one child and is where most off-by-one bugs enter.
  • •Taking the min instead of the max — that's the minimum-depth problem, and it has a genuine extra trap of its own around single-child nodes.
  • •Recursing on a very deep tree in a language with a small stack. The BFS version, counting levels off a queue, avoids it and is worth mentioning.