roadmap/trees/Binary Tree Right Side View

Binary Tree Right Side View

MediumFacebookAmazonGoogleBloomberg

Problem

Given the root of a binary tree, imagine standing on the right side. Return the values of the nodes you can see ordered from top to bottom.

Intuition — the key insight

BFS level order traversal — the last node at each level is what you see from the right. Collect the last element from each level's list.

Approach

BFS level order, take last of each level

Standard BFS with level snapshotting. For each level, add only the last element (index = level_size - 1) to the result.

Complexity

Time

O(n)

Space

O(n)

Visit every node. Queue holds at most one full level.

Solution code

Python

def rightSideView(self, root: TreeNode) -> List[int]:
    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:  # last node in level
                result.append(node.val)
            if node.left:  queue.append(node.left)
            if node.right: queue.append(node.right)
    
    return result

Edge cases to remember

⚠Left-skewed tree: all left children visible from right at each level

⚠Single node: return [root.val]