Maximum Depth of Binary Tree (LeetCode 104) Solution

The problem

You get the root of a binary tree. Return its maximum depth: the number of nodes on the longest path from the root down to any leaf. An empty tree has depth 0.

The tree arrives as a TreeNode with val, left and right (LeetCode supplies the class). Examples write it in level order, with null for a missing child.

Input:  [3, 9, 20, null, null, 15, 7]

        3
       / \
      9   20
         /  \
        15   7

Output: 3

The longest root-to-leaf path is 3 → 20 → 15 (or 3 → 20 → 7), which has three nodes.

How to think about it

Start with brute force. You could list every root-to-leaf path, measure each one, and keep the longest. That works, but building and storing every path is wasteful, and it doesn’t use the tree’s structure.

The key insight: depth is defined recursively. The deepest path from a node must go through either its left child or its right child. So depth(node) = 1 + max(depth(left), depth(right)). The 1 counts the node itself. An empty node contributes 0, and that is the whole base case.

Trust the recursion. You don’t have to picture the whole tree. Assume the recursive calls correctly return the depths of the two subtrees, then combine them. That’s the “recurse, combine, return” shape from the lesson in its purest form.

Which pattern is this? Tree DFS. The tell is “depth / height”, a value for the whole tree that is built from the same value for each subtree.

Approach

If the node is empty, return 0.
Recursively get the depth of the left subtree and of the right subtree.
Return 1 plus the larger of the two.

The answer for the root is the answer for the whole tree.

Solution

def max_depth(root):
    if not root: return 0                                    # empty tree has depth 0
    return 1 + max(max_depth(root.left), max_depth(root.right))   # me + deeper child
# tree [3,9,20,null,null,15,7] -> 3

Dry run

On the example tree. Calls finish bottom-up, so this is the order they return in:

Node	Left depth	Right depth	Returns
9	0	0	1
15	0	0	1
7	0	0	1
20	1	1	2
3	1	2	3

The root returns 3.

Complexity

Time: O(n). Each of the n nodes is visited exactly once and does O(1) work.
Space: O(h). The recursion stack is as deep as the tree’s height h. That is O(log n) for a balanced tree and O(n) for a skewed one (a “linked list” tree).

Edge cases and pitfalls

Empty tree (root is None) returns 0, handled by the base case.
Single node returns 1, not 0. Depth counts nodes here, not edges; check which one the question wants.
Skewed tree. A chain of 10,000 nodes will hit Python’s default recursion limit. An iterative BFS that counts levels avoids it.
Don’t use min by accident. Minimum depth is a different problem with a subtle trap (a node with one child is not a leaf).

Minimum Depth of Binary Tree (LeetCode 111): the mirror question, best solved with BFS.
Diameter of Binary Tree (LeetCode 543): the same depth function, plus a global best.
Binary Tree Level Order Traversal (LeetCode 102): count levels with BFS instead.