Maximum Depth of Binary Tree

How you get there

1. 1Depth of a node is one plus the deeper of its two subtrees.
2. 2An empty node contributes zero.
3. 3This is the template for almost every 'return something from each subtree' tree problem.

Solution

def max_depth(root) -> int:
    if not root:
        return 0
    return 1 + max(max_depth(root.left), max_depth(root.right))

Time

O(n)

Space

O(h)

What goes wrong

Returning 0 for a leaf instead of 1 shifts every answer by one; decide the convention first.