Given the root of a binary tree, imagine standing on its right side. Return the values of the nodes you can see, ordered top to bottom.
The visible node at each depth is the last node on that level (its rightmost node). Note a level's rightmost visible node may be a left child if the level has no node further right.
The tree is given as a level-order array where null marks a missing child: [1, 2, 3, null, 5, null, 4].
Example
Level 0: 1; level 1: rightmost is 3; level 2: 4.
Constraints
- The number of nodes in the tree is in the range [0, 100].
- -100 <= Node.val <= 100
Intuition
Standing to the right of the tree, you see the last node on each level. A direct solution does a breadth-first traversal collecting every level into its own array, then takes the last value of each.
function rightSideView(root) {
if (!root) return [];
const levels = [];
let queue = [root];
while (queue.length) {
const level = [];
const next = [];
for (const node of queue) {
level.push(node.val);
if (node.left) next.push(node.left);
if (node.right) next.push(node.right);
}
levels.push(level);
queue = next;
}
return levels.map((level) => level[level.length - 1]); // last of each level
}This is O(n) but stores every level in full just to keep one value from each. Can we trim the memory?
The key observation: we only need the last node of each level, so during the level scan we just push the node we happen to be on when it's the final one in the queue — no per-level array needed. This is the level-order / queue pattern, taking one value per level.
Note the visible node may be a left child if its level has nothing further right. Tracing [1, 2, 3, null, 5, null, 4] — root 1; level 1 is 2, 3; level 2 is 5 (2's right) and 4 (3's right). The lane is the BFS visit order; each action marks whether the node is its level's last (visible) node:
BFS visit order — the last node of each level is the visible one
Root is alone on its level, so it's the last — visible.
2 is the first of level 1; another node (3) follows, so 2 is hidden.
3 is the last of level 1 — visible.
5 is the first of level 2; 4 still follows.
4 is the last of level 2 — visible. Right-side view: [1, 3, 4].
Optimization
BFS, take the last of each level
Do a level-order (breadth-first) traversal. Process one full level at a time by snapshotting the queue size before draining it; the last node dequeued on a level is its rightmost, so push that value.
O(n) time, O(w) space for the queue (w = max level width).
function rightSideView(root) {
if (!root) return [];
const result = [];
let queue = [root];
while (queue.length) {
const next = [];
// The last node processed this level is the one visible from the right.
for (let i = 0; i < queue.length; i++) {
const node = queue[i];
if (i === queue.length - 1) result.push(node.val);
if (node.left) next.push(node.left);
if (node.right) next.push(node.right);
}
queue = next;
}
return result;
}Complexity analysis
Time complexity: O(n). Here's why:
- The level-order traversal visits each node once, doing O(1) work.
So O(n).
Space complexity: O(w). Here's why:
- The queue holds at most one level at a time — its width
w, up to ~n/2 at the bottom of a full tree.
So O(n) in the worst case. Unlike the brute force, no per-level array is retained.
Test cases
Beyond the example above, these are worth thinking through before you submit.
| Input | Expected output | Description |
|---|---|---|
| root = []null | [] | Empty tree — nothing visible. |
| root = [9]9 | [9] | Single node is visible. |
| root = [5,6,7]657 | [5,7] | Level 1's rightmost is 7. |
| root = [5,6,null,7]765 | [5,6,7] | A left-only spine: each node is its level's rightmost. |
| root = [5,6,7,8]8657 | [5,7,8] | Level 2's only node (left child 8) becomes visible. |
Try it yourself
Write your solution against the real judge before checking the reference.