Description
Return the value visible from the right side at each depth of a binary tree, from top to bottom. An empty tree yields an empty list. Input arrays use level order.
Solution
from collections import deque
def right_side_view(root):
queue = deque([root]) if root else deque()
result = []
while queue:
for _ in range(len(queue)):
node = queue.popleft()
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
result.append(node.val)
return resultExamples
Example 1
- Input
[[1,2,3,null,5,null,4]]- Output
[1,3,4]
The rightmost values at the three depths are 1, 3, and 4.
Example 2
- Input
[[1,2,null,3]]- Output
[1,2,3]
Left-only nodes remain visible.
Example 3
- Input
[[]]- Output
[]
An empty tree has no visible values.
Approach
Traverse one level at a time, adding children left before right. The final node in each level is its visible rightmost node.
Time & space
O(n) time and O(w) auxiliary space excluding output, where n is the node count and w is the widest level.