Binary Tree Right Side View

Medium#199tree nodes

You get the root of a binary tree, possibly none. Imagine standing to the right of it: list the values you can see, from the top down. On each level only the rightmost node is visible. Our example is the tree [6, 2, 9, 5, 4, none, 11, none, none, 8] in level order — the answer is [6, 9, 11, 8].

199 Binary Tree Right Side ViewWalkthrough · 1×

Example: list what is seen from the right of a tree whose right edge ends one level early.

62954118queuefront on the left—
not reachedin the queue, this levelin the queue, next levelcurrentdone

The root is 6, not none

01/58
restart · back · play · step
Speed
1function rightSideView(root):
2 if root is none:
3 return []
4 result = []
5 queue = [root]
6 while queue is not empty:
7 size = queue.size
8 for i from 1 to size:
9 node = queue.popFront()
10 if i == size:
11 result.add(node.val)
12 if node.left is not none:
13 queue.pushBack(node.left)
14 if node.right is not none:
15 queue.pushBack(node.right)
16 return result
state
result
–
queue
–
size
–
i
–
node
–
historyclick a step to go back

← → step · space play/pause

Why it works

  1. BFS takes a level left to right, and size says how many nodes it has, so i == size marks its rightmost node.
  2. Looking from the right, you see the rightmost node of each level, whichever subtree it hangs in: following right children alone would miss 8.
  3. Every level gets exactly one value, in order from the top, so the list is the view.

Complexity

Time O(n): each node enters and leaves the queue once. Memory O(w): the queue holds at most about two levels, w is the widest one.

nextNow solve it yourself, no hints.

Solve on LeetCode ↗

The problem and its statement belong to LeetCode. Here are our own retelling, example and solution. Patterns Hero is not affiliated with LeetCode.