Medium Level-order BFS Trees
In plain English: Imagine looking at a binary tree from the right side. List what you'd see from top to bottom.
BFS level by level. The last node in each level is visible from the right. Alternatively, DFS visiting right before left, recording the first node at each new depth.
Prompt
Given the root of a binary tree, return the values of nodes visible from the right side, ordered from top to bottom.
Try to write it from scratch before scrolling down.
Solution
from collections import deque
def right_side_view(root):
if not root:
return []
result = []
queue = deque([root])
while queue:
level_size = len(queue)
for i in range(level_size):
node = queue.popleft()
if i == level_size - 1: # rightmost in this level
result.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
return result
# Test: tree [1,2,3,null,5,null,4]
# right_side_view => [1,3,4]