Maximum Depth in BT
MediumOne plus the deeper child
Problem
Return the maximum depth (height) of a binary tree.
Depth = 1 + the taller of the left and right subtree depths.
The idea
The depth of a tree is one more than the greater of its subtrees' depths, with an empty tree at zero. It is the archetypal postorder computation: both children first, then combine.
The trick
- Base case: null returns 0.
- O(n) time, O(height) stack.
Step 1 of 8. A node's height is 1 + the taller of its two subtrees. Solve leaves first, then bubble up.
1/8
Optimal
timeO(n)spaceO(h)
Combine children heights.
1function height(node) {2 if (!node) return 0;3 return 1 + Math.max(height(node.left), height(node.right));4}Input
- nodes
- 6, 5 edges
Output
- max depth
- —
- answer
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- tree = [3,9,20,null,null,15,7]
- Output:
- 3
- Explanation:
- The longest root-to-leaf path has 3 levels.
Example 2
- Input:
- tree = [1,null,2]
- Output:
- 2
- Explanation:
- Root plus one child → depth 2.
Example 3
- Input:
- tree = []
- Output:
- 0
- Explanation:
- An empty tree has depth 0.
Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.