FAANGPrep Sprint

Binary Tree Rightmost Node (Right Side View)

List the node visible on each level when the tree is viewed from the right, top level first.

Medium

10 min

Solve on LeetCode

Examples

Input:root = [1,2,3,null,5,null,4]

Output:[1,3,4]

Explain:

The last node of each level.

Input:root = [1,2,3,4,null,null,null,5]

Output:[1,3,4,5]

Explain:

5 is a left child, but nothing on the right reaches its depth.

Input:root = [1,null,3]

Output:[1,3]

Explain:

One node per level.

Input:root = []

Output:[]

Explain:

Nothing to see.

Problem Understanding

Picture the binary tree under root from its right side. List the value of the node visible on each level, from the top level down.

Essentially: For every level, pick the last node.

Algorithm Strategy

We can use BFS (Level Order Traversal).

Process the tree level by level.
Each level is dequeued left to right, so the node dequeued at position size - 1 — the last of its level — is the rightmost node.
Add that node's value to our result list.

Interactive Visualization

iN = POSITION IN THE LEVEL · GREEN = SEEN FROM THE RIGHT

ENQUEUE ROOT

—

size

—

queue (front first)

result

[]

Put the root, 1, in the queue

A new level: size = 1. The node dequeued at position 0 is the one seen from the right

Tree

Legend & Complexity

The node just dequeued; iN is its position in the level

Waiting in the queue

The last node of its level — the one seen from the right

Time

O(n)

Space

O(w) queue, w = widest level

Each node on the level being processed carries its position, i0, i1, …. The node dequeued at position size − 1 is the one visible from the right, and it stays green. Try Example 2: the rightmost node on the deepest level is a left child.

Dry Run

Tree: [1, 2, 3, null, 5, null, 4] — root 1; 2 has a right child 5; 3 has a right child 4.

Level	Nodes	Rightmost	Result
0	`[1]`	1	`[1]`
1	`[2, 3]`	3	`[1, 3]`
2	`[5, 4]`	4	`[1, 3, 4]`

Edge Cases & Common Mistakes

Edge Cases:

Null Root: Return [].
Left-skewed Tree: You still see the left nodes if there are no right nodes blocking them (Right Side View != Right Children only!).

Common Mistakes:

Only traversing node.right. (Wrong! You might see left children if the right side is shorter).

Solution Code

BFS approach.

Binary Tree Rightmost Node (Right Side View) Code

1var rightSideView = function(root) {
2    const result = [];
3    if (!root) {
4        return result;
5    }
6    const queue = [root];
7    let head = 0;
8    while (head < queue.length) {
9        const size = queue.length - head;
10        for (let i = 0; i < size; i++) {
11            const node = queue[head++];
12            if (i === size - 1) {
13                result.push(node.val);
14            }
15            if (node.left) {
16                queue.push(node.left);
17            }
18            if (node.right) {
19                queue.push(node.right);
20            }
21        }
22    }
23    return result;
24};