Binary Tree Right Side View (LeetCode 199)

The problem

You get the root of a binary tree. Imagine standing to its right and looking left. Return the values of the nodes you can see, from top to bottom: one per level, the rightmost node on that level.

Input:      1
           / \
          2   3
           \   \
            5   4

Output: [1, 3, 4]

From the right you see 1 on level 0, 3 on level 1, and 4 on level 2. 2 and 5 are hidden behind them.

How to think about it

Start with the tempting wrong idea. “Rightmost” makes people walk down the right edge: root, root.right, root.right.right, …. That fails as soon as the right side is shorter. In [1, 2, 3, 4], node 4 hangs off the left child 2, but nothing is to its right on level 2, so it’s visible. The right edge alone gives [1, 3] and misses it.

The key insight: “visible from the right” means “last node on its level”. Every level contributes exactly one visible node, and it’s whichever node is furthest right on that level, no matter which branch it came from. So this is a level question, and level questions are BFS.

Use the standard level loop and keep only the last element. With children pushed left before right, each level is popped left to right. Snapshot n = len(q); the node popped at index i == n - 1 is the rightmost one. Record it.

Which pattern is this? Tree BFS. The tell is “for each level, pick one node” (rightmost, leftmost, largest). A DFS that visits right before left and records the first node seen at each new depth also works, in O(h) space.

Approach

1. If root is None, return [].
2. Put root in a queue.
3. While the queue is not empty:
   • n = len(q),
   • for i in 0 .. n-1: pop a node; if i == n - 1, append its value to res; push its left then right child.
4. Return res.

Solution

from collections import deque

def right_side_view(root):
    if not root: return []
    res = []; q = deque([root])
    while q:
        n = len(q)                                # size of the current level
        for i in range(n):
            node = q.popleft()
            if i == n - 1: res.append(node.val)   # last on this level = visible from the right
            if node.left: q.append(node.left)
            if node.right: q.append(node.right)
    return res
# right_side_view([1,2,3,null,5,null,4]) -> [1,3,4]

Dry run

On the example tree:

Complexity

• Time: O(n). Each node is pushed and popped once.
• Space: O(w), the widest level in the queue; O(n) in the worst case.

Edge cases and pitfalls

• Empty tree: returns [].
• Left branch deeper than the right: right_side_view([1,2,3,4]) returns [1, 3, 4]; the 4 comes from the left subtree.
• Only following .right pointers. The classic wrong answer; see above.
• Pushing right before left flips the level order, so you’d need to keep the first node instead. Pick one convention and stay consistent.
• Left side view is the same code with i == 0.

Related problems

• Binary Tree Level Order Traversal (LeetCode 102): the full level lists this view is taken from.
• Populating Next Right Pointers in Each Node (LeetCode 116): also cares about each node’s right-hand neighbour on its level.
• Average of Levels in Binary Tree (LeetCode 637): another single-value-per-level summary.