Binary Tree Right Side View

Problem in plain words

Imagine standing to the right of a binary tree and looking at it. On each level you can see only the rightmost node; everything else on that level is hidden behind it. Return the values you can see, from the top level to the bottom.

Example: root 1 with children 2 and 3, where 2 has a left child 4. Level 0 shows 1, level 1 shows 3, and level 2 shows 4 — even though 4 hangs on the left side, it is the only node on its level. The answer is [1, 3, 4].

Intuition

"One value per level" is a strong hint for a level-order traversal. If a BFS enqueues the left child before the right child, each level is processed left to right, so the last node processed on that level is exactly the one visible from the right.

Approach

1. If the root is null, return an empty list.
2. Put the root in a queue.
3. While the queue is not empty, read its current size — that is the number of nodes on this level.
4. Pop exactly that many nodes, pushing each one's left then right child. Remember the last node popped.
5. Append the last node's value to the answer and continue with the next level.

Dry run

Java solution

class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> view = new ArrayList<>();
        if (root == null) {
            return view;
        }
        Deque<TreeNode> queue = new ArrayDeque<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                if (i == size - 1) {
                    view.add(node.val);
                }
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
        }
        return view;
    }
}

Python solution

class Solution:
    def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
        if root is None:
            return []
        view = []
        queue = deque([root])
        while queue:
            size = len(queue)
            for i in range(size):
                node = queue.popleft()
                if i == size - 1:
                    view.append(node.val)
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
        return view

Complexity

Edge cases and common mistakes

• Only following right children — a left node is visible when the right side of that level is empty, as with 4 above.
• Reading the queue size inside the loop condition — the queue grows while you process a level, so capture size before the inner loop.
• Empty tree — return an empty list rather than crashing on root.val.