Deepest Leftmost Value
MediumTrees
Problem
Given the root of a non-empty binary tree, return the value of the leftmost node on the deepest level.
Example 1
- Input:
- root = [2, 1, 3]
- Output:
- 1
Example 2
- Input:
- root = [1, 2, 3, 4, null, 5, 6, null, null, 7]
- Output:
- 7
The deepest level contains only 7, which hangs under 5 on the right side of the tree.
Constraints
- 1 ≤ number of nodes ≤ 10^4
- -2^31 ≤ node.val ≤ 2^31 - 1
Hint
Show the first hint
Two conditions: deepest first, then leftmost. Which traversal makes 'deepest' easy?
Walkthrough
How to approach it
01Clarify before coding
- Is 'leftmost' the leftmost leaf of the tree? No, it is the leftmost node of the deepest level, which may sit in the right subtree.
- Can the tree be empty? No, at least one node.
- Can values be negative or extreme? Yes, but we only return them.
02Brute force
Compute the height first, then run a second traversal to find the first node at that depth.
Cost: O(n) time but two passes and extra bookkeeping.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.