Example 1
ready- Input
root = [ 1, 2, 3, null, 5, null, 4 ]- Expected
[ 1, 3, 4 ]- Why
- the last nodes across the three levels are 1, 3, and 4
Rightmost Node
35 min · rightSideView()mediumOpen in LeetCode #199 ↗
A tree can hide most of its branches when you photograph it from the right. At each height, only the node farthest to that side stays visible.
Given the root of a binary tree, return its right-side view — the last node you meet at every depth when that level is read from left to right. List the values from the root downward.
Watch two details:
- The visible node can come from the left subtree when no node farther right reaches that depth.
- You return one value per non-empty depth, not every node with a missing right child.
- An empty tree returns
[].
Constraints
0 <= node count <= 10_000-1_000 <= node.val <= 1_000
Hints
Think one level at a time
If you already had all nodes from one depth in left-to-right order, which single position would you keep?
Freeze the queue length
Save the number of queued nodes before processing a level. The node handled at the final index of that group is the one visible from the right.
A depth-first alternative
Visit right children before left children. The first node you reach at a new depth is that depth's rightmost node.
Follow-up
How would the traversal change if you wanted the left-side view instead?
Visible cases
Examples
Example 2
ready- Input
root = []- Expected
[]- Why
- an empty tree has no visible nodes
Example 3
ready- Input
root = [ 1, 2, 3, 4, null, null, null, 5 ]- Expected
[ 1, 3, 4, 5 ]- Why
- the left subtree supplies the view after the right subtree ends
Interview signal
Asked at
AmazonMetaGoogle
Right-first DFS — keep the first arrival
A depth-first search (DFS) follows one branch before returning to another. Use a stack, a last-in, first-out collection, and visit the right child before the left child; then the first node you reach at each new depth is the rightmost one.
def right_side_view(root: TreeNode | None) -> list[int]:
if root is None:
return []
view: list[int] = []
stack: list[tuple[TreeNode, int]] = [(root, 0)]
while stack:
node, depth = stack.pop()
if depth == len(view):
view.append(node.val)
if node.left is not None:
stack.append((node.left, depth + 1))
if node.right is not None:
stack.append((node.right, depth + 1))
return viewThe stack removes its last item first, so pushing left before right makes the right child
run next. If h is the tree's number of levels, the pending path uses O(h) space.
Time O(n) — every node is visited once. Space O(h) — the DFS stack and returned view each grow with the height.
Last node per level — let BFS expose it
The direct pattern is breadth-first level-order traversal (BFS): visit every node at
one depth before moving down, using a queue, a first-in, first-out collection. The
level-size trick means saving len(queue) before processing; the final node among
those saved slots is the rightmost node for that level.
from collections import deque
def right_side_view(root: TreeNode | None) -> list[int]:
if root is None:
return []
view: list[int] = []
queue = deque([root])
while queue:
level_size = len(queue)
for index in range(level_size):
node = queue.popleft()
if node.left is not None:
queue.append(node.left)
if node.right is not None:
queue.append(node.right)
if index == level_size - 1:
view.append(node.val)
return viewEnqueue children in normal left-to-right order. That makes the last removal from each saved group exactly the value you need.
Time O(n) — each node enters and leaves the queue once. Space O(w) auxiliary —
the queue grows to the tree's widest level, whose size is w.
Loading editor
Console
ready to runReady to run.
3 cases are queued.
Visible testcase
Case 1
Expected
[ 1, 3, 4 ]
Run: visible + custom · Submit: full suite