Given the root of a binary tree, return its maximum depth. That is the number of nodes on the longest path from the root down to a leaf.
DSA Animator › DSA Revision › Tree › Maximum Depth of Binary Tree
Remember: depth equals 1 plus the deeper child. Counting levels with a breadth first search gives the same answer. The video solves Maximum Depth of Binary Tree (LeetCode 104, Easy) with the DFS Height pattern from the Tree topic, and you can replay every step in the interactive Maximum Depth of Binary Tree animation.
Given the root of a binary tree, return its maximum depth. That is the number of nodes on the longest path from the root down to a leaf.
For the tree 3, 9, 20, 15, 7, the depth is 3. The longest paths are 3, 20, 15 and 3, 20, 7.
You could list every root to leaf path and take the longest one. But storing every path is unnecessary, because only the length matters.
The depth of a tree is 1 for the root, plus the deeper of its two subtrees. An empty tree has depth 0, and that is the base case. So the recursion asks each child for its depth, and passes the answer up.
The leaf 9 has two empty children, so its depth is 1. The leaves 15 and 7 also have depth 1. Node 20 has depth 1 plus the larger of 1 and 1, which is 2. The root 3 has depth 1 plus the larger of 1 and 2, which is 3. So the maximum depth is 3.
In code, return 0 when the root is null. Otherwise return 1 plus the maximum of the depth of the left child and the depth of the right child. Every node is visited once, so it's O of n time and O of the height in stack space.
Remember: depth equals 1 plus the deeper child. Counting levels with a breadth first search gives the same answer.