Binary Tree Right Side View
1Try it yourself first
Think for 20-30 minutes before you open any hint. Being stuck is where the learning happens.
Only for you, saved in this browser. After you see the approach you will compare it with your idea.2What is being asked
Imagine standing on the right of the tree. Return the nodes you can see, top to bottom.
3Hint ladder
Take one rung at a time. Stop as soon as the idea clicks.
- Hint 1Which node of a level hides the others when viewed from the right?
- Hint 2Do a level-by-level walk and keep the last value of each level.
4The approach
Have you tried the hints? The approach is built as a path from the obvious way to the clever one.
Standing beside a tall building and looking at it from the right, on each floor you see only the room closest to you; the rooms to its left are hidden behind it. So for each floor the answer is simply the last room when you list that floor from left to right.
- The obvious way
Traverse the whole tree recording depth for each node, then pick the rightmost per depth: same idea, more bookkeeping.
- The key insight
Use the level-order walk with a queue. When serving a level, remember the value of the last node taken: that is what is visible from the right.
- The algorithm
- Queue starts with the root.
- For each level (queue's size at the start of the round), serve that many nodes.
- Keep the value of the LAST node served in this level.
- Add children to the queue; after all levels, return the saved values.
Watch it run
Exampletree = [1, 2, 3, null, 5, null, 4]
Level 1 has only the node 1: it is visible.
visible: 1
Where people slip
- The visible node can be on the LEFT side of the tree when the right side is shorter; that is why we take the last of each level, not just walk right children.
How close was your idea?
You did not write an idea, and that is fine.
Be honest with yourself. This sets your revision list.
5Code
Try writing it yourself from the steps first. Then compare.
from collections import deque
def right_side_view(root):
seen = []
queue = deque([root] if root else [])
while queue:
size = len(queue) # exactly one level
for position in range(size):
node = queue.popleft()
if position == size - 1:
seen.append(node.val) # the last node of the level is visible
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
return seenNow close this and write it again from memory, in the language you will use in the interview. Reattempt after 1 day, 7 days and about 30 days.
6Still stuck? Watch a video
Seeing someone explain it out loud can make it click. Try the video after you have read the approach above.