Maximum Depth of Binary Tree

Return the maximum depth of a binary tree: the number of nodes on the longest root-to-leaf path.

A way to picture it

A company wants to know how many management levels it has. The CEO doesn't count everyone — she asks her two direct reports how deep their teams go, takes the bigger answer, and adds one for herself. Everyone below does the same.

How to approach it

depth(node) = 1 + max(depth(left), depth(right)), with depth(null) = 0. Trust the recursion to answer for each subtree.

Example

Input: {"root":[3,9,20,null,null,15,7]}. Output: 3.

Complexity: O(n) time and O(h) space. Every node is visited once; the call stack is as deep as the tree.

This page includes an animated walkthrough, Java and Python solutions, and a question to check your understanding.