Skyline From the East
MediumTrees
Problem
Picture a binary tree drawn on a wall, root at the top. Standing to the right of the drawing, you see exactly one node per level: the one farthest to the right on that level (nodes behind it are hidden).
Given the root, return the values you can see, from the top level down.
Example 1
- Input:
- root = [1, 2, 3, null, 5, null, 4]
- Output:
- [1, 3, 4]
Example 2
- Input:
- root = [1, 2, 3, 4]
- Output:
- [1, 3, 4]
On the third level the only node is 4, which hangs on the left branch but is still visible from the right.
Constraints
- 0 ≤ number of nodes ≤ 10^4
- -100 ≤ node.val ≤ 100
Hint
Show the first hint
Visibility is decided per level. Which traversal naturally groups nodes by level?
Walkthrough
How to approach it
01Clarify before coding
- Is it always the rightmost child of the previous visible node? No: a deeper left branch can show through, as in [1, 2, 3, 4].
- Empty tree? Return [].
- One value per level? Yes, exactly one per non-empty level.
02Brute force
Follow right pointers from the root.
Cost: O(h), but wrong: it misses levels that exist only under left branches.
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.