Binary Tree Right Side View

Given the root of a binary tree, imagine standing on its right side. Return the values of the nodes you can see, ordered from top to bottom — that is, the rightmost node at each level.

The tree is given in level-order (breadth-first), using null for missing children.

Hints

· Stuck? Reveal one nudge at a time.

The visible node at each level is the rightmost one.

In level-order BFS that's simply the last node dequeued on each level.

A DFS that goes right before left records the first node it reaches at each new depth.

Common doubts

No — if a level's rightmost node lacks a right child, the visible node can descend from a left child; it's the rightmost node, not the right child.

Going right before left, the first node reached at any depth is the rightmost at that depth, so you record on first arrival.

The same idea mirrored: the first node of each level in BFS, or a left-first DFS.

Interview follow-ups

· What an interviewer asks next.

Take the first node of each level in BFS, or recurse left-before-right and record the first node at each depth.

Group nodes by horizontal distance instead of level, keeping the first (top) or last (bottom) node per column.

Fun facts

The right-side and left-side views are exact mirrors: swap 'first' and 'last' of each level.
Right-first DFS is a neat way to compute the view with O(height) space instead of O(width).

Asked at

AmazonFacebookMicrosoft

Frequently Sometimes Occasionally

Example 1

Input: root = [1, 2, 3, null, 5, null, 4]
Output: [1, 3, 4]
From the right you see 1 (level 0), 3 (level 1), and 4 (level 2).

Example 2

Input: root = [1, null, 3]
Output: [1, 3]
Only the right spine is visible.

Example 3

Input: root = []
Output: []
An empty tree shows nothing.

Constraints

- The number of nodes is in the range [0, 100] - -100 <= Node.val <= 100

Standing on the right, the node you see at each level is the rightmost one. So this is level-order traversal where you keep only the last node of each level. Equivalently, a depth-first walk that visits the right child first and records the first node it reaches at each new depth.

Prerequisites

Before you start

· Concepts used directly in the solution.

Level-order traversal. BFS by level — the last node of each level is the right-side view.

Depth-tracking DFS. Right-first DFS records the first node seen at each depth.

Clarifying questions

Questions to ask first

· Signals seniority before you write a line of code.

Definition

“Rightmost node, or only right children?”

The rightmost node at each level, which may be a left child if the right side is missing.

“Empty tree?”

Return an empty list.

The ideal opening — say it like this

The right-side view is the last node of each level, so I run level-order BFS and keep the final node of every level.

Or I DFS right-child-first and record the first node I reach at each new depth.

Understand the problem

Worked example — tree [1, 2, 3, null, 5, null, 4]

        1
       / \
      2   3
       \   \
        5   4
level 0: rightmost 1
level 1: rightmost 3
level 2: rightmost 4
result: [1, 3, 4]

Key observations

1Aha

Right-side view = last node per level

It's level-order with everything but each level's final node discarded.

2Aha

A left child can be visible

If a level's rightmost node has no right child, its rightmost may descend from a left child — 'rightmost', not 'right child'.

3Aha

Right-first DFS is equivalent

Recursing right before left reaches each depth's rightmost node first; record on first arrival at a depth.

Brute force vs optimal

	Right-first DFS	BFS last-of-level
Idea	Record first node reached at each new depth	Keep the last node dequeued per level
Time	O(n)	O(n)
Space	O(height)	O(n)

Both are O(n); BFS reads most directly as 'last of each level'. Full code is in the Approaches selector below.

Summary

Key takeaway

The right-side view is the rightmost (last) node at each level. Take it from level-order BFS, or from a right-first DFS that records the first node at each new depth. O(n) time.

bfs level by level:
    append the last node of each level to the result