Find the maximum depth (height) of a binary tree.

How to think about it

This question looks like it’s about depth, but the interviewer is really checking whether you reach for recursion when a tree property depends on its children. Depth, diameter, balance, path sum — they all share one shape: you cannot answer for a node until both children have answered for themselves. The tell is that you can write f(node) = combine(f(node.left), f(node.right)). The moment a problem fits that mold, post-order DFS is the tool, and you should say so rather than reaching for a level-by-level BFS that’s more code for the same answer.

For depth the combine step is tiny. The depth of the tree rooted at a node is 1 + max(depth(left), depth(right)) — one for the node itself, plus however deep the taller child goes. The recursion has to stop somewhere, and the natural floor is None: an empty subtree has depth 0. That single base case plus the one-line recurrence is the entire solution; each call simply trusts its two children to report back, then adds one.

A worked example

class TreeNode:
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def max_depth(root):
    if root is None:
        return 0                    # empty subtree contributes nothing
    return 1 + max(max_depth(root.left), max_depth(root.right))

# tree: 3 -> (9, 20 -> (15, 7))
root = TreeNode(3, TreeNode(9), TreeNode(20, TreeNode(15), TreeNode(7)))
print(max_depth(root))              # 3 -> 20 -> (15 or 7)

print(max_depth(TreeNode(1)))       # single node
print(max_depth(None))              # empty tree

# a skewed, linked-list-shaped tree
skewed = TreeNode(1, TreeNode(2, TreeNode(3, TreeNode(4))))
print(max_depth(skewed))            # one long arm

3
1
0
4

The first tree’s longest root-to-leaf path runs 3 → 20 → 15 (or 7), three nodes deep, so the answer is 3 — the shallow 9 branch never wins the max. A lone node is depth 1, an empty tree is 0, and the skewed tree is effectively a linked list of four nodes, so its depth is 4. Each result is just the longest chain of +1s the recursion can stack before it hits None.