Maximum Depth of Binary Tree

Problem

Given the root of a binary tree, return its depth: the number of nodes on the longest path from the root down to any leaf. An empty tree has depth 0 and a single node has depth 1.

• The tree has at most 50,000 nodes and may be empty.
• Node values are integers; they play no role in the answer.

Examples

• root = [8, 4, 12, 2, None, None, 15, 1] → 4. The longest root-to-leaf path is 8 → 4 → 2 → 1; the right side only reaches depth 3.
• root = [5, None, 9] → 2. A right-skewed tree of two nodes.
• root = [] → 0. No nodes, no path.

Hints

1. If you knew the depth of each subtree, how would you get the depth of the whole tree?
2. What is the depth of an empty tree? Getting that base case right makes the recursion fall out.
3. Post-order DFS returning 1 + max(depth(left), depth(right)); or BFS counting how many levels you dequeue.