The problem
Imagine standing on the right side of a binary tree. Return the values you can see, from top to bottom.
Input: [1, 2, 3, null, 5, null, 4] Output: [1, 3, 4]
Picture it
Picture yourself standing to the right of the tree, looking left. On each row (level) you can only see the node nearest to you: the rightmost one, which hides the others behind it. A level-by-level walk tells us the last node in each row.
How to recognise it
- The answer has one value per level: the node you would see from the right.
- That is the last node of each level in left-to-right order, so the problem is level order traversal with a small change.
- The rightmost node is not always on the right edge: if a level has nothing on the right, a left-side node shows through.
- Up to 100 nodes, so any approach that visits each node once is plenty.
Start with brute force
For each depth d = 0, 1, 2, ..., search the tree right child first and stop at the first node found at depth d. Stop when a depth has no nodes.
def right_view_brute(root):
view, d = [], 0
while True:
found = []
def rightmost(node, depth):
if not node or found:
return
if depth == d:
found.append(node.val)
return
rightmost(node.right, depth + 1)
rightmost(node.left, depth + 1)
rightmost(root, 0)
if not found:
return view
view.append(found[0])
d += 1
Each depth starts again from the root, so the levels above are walked again every time: up to O(n · h) time, where h is the height. With at most 100 nodes that is at most about 10^4 steps, so it passes; the point is the cleaner one-pass method.
From brute force to the idea
- Find the waste. Each depth re-walks every level above it.
- Go level by level once. A breadth-first search (BFS: visit all nodes at one distance before any farther ones) with a
dequeprocesses the tree in rounds, one level per round, children pushed left before right. - Read the view before the round. At the start of a round the queue holds exactly one level, in left-to-right order. Its last item,
q[-1], is the rightmost node of that level. The shown code records it, then pops the round'slen(q)nodes and pushes their children. - Start safely.
deque([root] if root else [])makes an empty tree give an empty queue, so the loop never runs.
This is the key idea: run level order BFS and keep the last node of every level.
A depth-first version also works: visit right before left, and record a node when its depth equals the number of values seen so far. The shown code needs from collections import deque.
The key idea
BFS by levels and keep the last value of each level. O(n).
Python solution
def right_side_view(root):
view, q = [], deque([root] if root else [])
while q:
view.append(q[-1].val) # last in the row is visible
for _ in range(len(q)):
node = q.popleft()
if node.left: q.append(node.left)
if node.right: q.append(node.right)
return viewLeetCode adds the imports for you. To run this on your own machine, put this at the top: from collections import deque
In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.
Complexity
| Approach | Time | Space |
|---|---|---|
| Brute force (one search per depth) | O(n · h): levels above are re-walked for every depth | O(h): recursion stack |
| BFS, last of each level (shown code) | O(n): each node enters and leaves the queue once | O(w): the queue holds about one level, w is the widest level |
Edge cases
- Empty tree: returns
[]. - Left-only branch:
[1, 2]gives[1, 2]; the 2 is visible because nothing is to its right. - Deeper level reached only from the left (
[1, 2, 3, 4]): gives[1, 3, 4]; node 4 is under 2, not under 3. - Every level full: the view is just the right edge.
- No recursion: a deep chain is fine.
Common mistakes
- Following only right children from the root, which misses deeper levels that exist only on the left.
- Reading
q[-1]after the inner loop instead of before it; by then the queue holds the next level. - Pushing the right child before the left, which makes
q[-1]the leftmost node instead. - Forgetting the empty-tree case, so
deque([None])reachesNone.val.
Return the largest value on each level (LeetCode 515). For [1, 3, 2, 5, 3, null, 9] the answer is [1, 3, 9]. Describe your approach, then write it if you like.
Compare with our answer
Same BFS in rounds. Instead of the last node of the round, take the maximum value over the nodes in the queue at the start of the round.
from collections import deque
def largest_values(root):
out, q = [], deque([root] if root else [])
while q:
out.append(max(node.val for node in q))
for _ in range(len(q)):
node = q.popleft()
if node.left: q.append(node.left)
if node.right: q.append(node.right)
return out
Time O(n): each node is read once by max and popped once. Space O(w). Values may be negative, so do not start a running maximum at 0.
A strong answer mentions: that the queue holds exactly one level when the round starts, taking a maximum instead of the last item, and negative values.
1. You must list, for each floor of an org chart, the newest employee on that floor (children are stored oldest first). Which approach fits best?
"Last on each level" is exactly the right side view: BFS rounds give one level at a time and the last item is the one you want. Following only the newest reports misses floors reached through older ones.
2. Why can the shown code read the visible node as q[-1] before popping?
Rounds keep exactly one level in the queue at the start, pushed left before right, so the last item is that level's rightmost node. q[-1] only reads it; the node may be a left child.
3. A learner walks only node.right from the root and records each value. Which tree still gets the right answer?
When every level's rightmost node lies on the right edge, the shortcut works: [1, 3, 4]. In the other trees the deepest level is reached through a left child, so the right-only walk stops one level early.
Score 60% or more and the lesson is marked complete.