Rightmost Node

Medium

Last node of every level

Problem

Given a binary tree, return the values of the nodes you can see from the right side, top to bottom (the last node of each level).

In simple words

Look at each level from the side: keep the last node you'd see on every row.

The idea

Run a level-order traversal and keep only the final node dequeued on each level — that is the one visible from the right. Because BFS visits a level strictly left to right, no comparison of depths or positions is needed.

The trick

The last node popped in a level pass is the rightmost one.
For the left view, take the first node of each level instead.

←→stepspaceplay

1/5

Optimal

timeO(n)spaceO(n)

Fix the level width up front.

1const q = [root], out = [];2while (q.length) {3  const level = [];4  for (let n = q.length; n > 0; n--) {5    const node = q.shift();6    level.push(node.val);7    if (node.left) q.push(node.left);8    if (node.right) q.push(node.right);9  }10  out.push(level);11}

Input

nodes: 6, 5 edges

Memory

levels: —

Output

answer: —

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:: tree = [1,2,3,null,5,null,4]
Output:: [1, 3, 4]
Explanation:: The rightmost node on each level → 1,3,4.

Example 2

Input:: tree = [1,2,3]
Output:: [1, 3]
Explanation:: 1 then 3.

Example 3

Input:: tree = [1]
Output:: [1]
Explanation:: Just the root.

Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.