Maximum Depth of Binary Tree
You get the root of a binary tree. In a binary tree every node has at most two children, called left and right.
Return the maximum depth of the tree: the number of nodes on the longest path from the root down to a leaf. An empty tree has depth 0.
In the tests the tree is written in level order, with null for a missing child, so [3, 9, 20, null, null, 15, 7] is a tree with root 3, children 9 and 20, and 20 has children 15 and 7.
Examples
Input root = [3, 9, 20, null, null, 15, 7]
Output 3
Input root = [1, null, 2]
Output 2
Input root = []
Output 0
An empty tree.
Constraints
- 0 <= number of nodes <= 500
- -100 <= node value <= 100
Stuck? Take one hint at a time
Common mistakes
- Returning 1 for an empty tree, so the answer is off by one everywhere.
- Adding the depths of the two subtrees instead of taking the larger one.
- Forgetting the base case, so the recursion reaches an empty child and crashes on its left pointer.
- Counting edges instead of nodes, when the problem counts nodes.
Questions an interviewer may ask next
- Find the minimum depth: the shortest path to a leaf. (Careful with a node that has only one child.)
- Find the depth of the tree if it is an N-ary tree (each node has any number of children).
- Return the number of nodes on the longest path, and then the path itself.
- What is the largest stack depth your recursion needs, and how would you avoid it? (Use the level by level version.)
root
[3,9,20,null,null,15,7]
Expected output
3
Run checks these cases. Submit also runs hidden cases, and shows you the first one that fails.