Maximum Depth of Binary Tree

Find how many levels the tree has: the number of nodes on its longest path from the root down to a leaf. An empty tree has depth 0.

For [3,9,20,null,null,15,7], the longest paths are 3 → 20 → 15 and 3 → 20 → 7, so the depth is 3.

A node's depth is one more than the deeper of its two subtrees:

max_depth(node) = 1 + max(max_depth(node.left), max_depth(node.right))

An empty child is 0 deep, which ends the recursion. Each call waits for its left subtree's answer, then its right's, then returns. The answers flow up from the leaves.

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

Breadth-first search works too: count the levels a level-order traversal drains. Both visit every node once.

Run it on [3,9,20,null,null,15,7].

max_depth(3) calls itself on 9 first. Both of 9's children are None and return 0, so 9 returns 1.

Then 3 waits on 20. Its children, 15 and 7, are leaves that return 1 each, so 20 returns 1 + max(1, 1) = 2.

Back at the root, left = 1 and right = 2, and it returns 3.

• Return 0 for an empty child, not 1, or every depth comes out one too big.
• Take the larger side. [1,2,null,3,null,4] leans all the way left and is 4 deep.
• Count nodes, not edges: a single node is 1 deep.
• A chain of 10,000 nodes recurses 10,000 calls deep, past Python's default limit. Counting levels with a queue avoids that.

Each node gets one call, and each call does constant work besides its two recursive calls, so time is O(n).

The call stack holds one call per level of the current path, so space is O(h), where h is the tree's height. That's O(log n) for a balanced tree and O(n) for a chain.