Binary Tree Right Side View: Last Node Standing Per Level

If you interview at Meta, Amazon, Bloomberg, expect some version of "Binary Tree Right Side View". It is rated Medium, and it falls squarely into the Tree BFS pattern — pattern-first preparation beats grinding random problems every time. Part 6 of 11 in the Tree BFS arc.

The Problem

Standing to the right of a binary tree, return the values visible top to bottom — the rightmost node of each level. A Meta staple. Note it is not the right spine: a deep left subtree pokes into view wherever the right side runs out.

Input:  root = [1, 2, 3, None, 5, None, 4]
Output: [1, 3, 4]
For [1, 2, 3, 4] the answer is [1, 3, 4] — node 4 is visible from the left subtree.

Recognizing the Tree BFS Pattern

Breadth-first search explores a tree or graph level by level using a queue, and its defining superpower is the level snapshot: freeze the queue length, process exactly that many nodes, and you have processed one complete level. Anything phrased per-level — level lists, level averages, rightmost visible node, shortest path in unweighted structures — is BFS by construction.

Per-level selection (the last one) rather than per-level collection — the snapshot loop where you keep one value per round. The follow-the-right-child heuristic fails exactly when a left subtree outlives the right, which is the test case they will run.

The Approach

Snapshot loop; inside the level, remember the value at the final index (or overwrite a variable each pop — the last write wins). Append per level.

The DFS alternative — root-right-left preorder, recording the first node at each new depth — is elegant and worth naming for the left-side-view symmetry, where it needs only the child-order swapped.

Python Solution

class TreeNode:
    def __init__(self, val: int = 0, left: "TreeNode | None" = None,
                 right: "TreeNode | None" = None):
        self.val = val
        self.left = left
        self.right = right


from collections import deque


def right_side_view(root: TreeNode | None) -> list[int]:
    """Rightmost value of each level, top to bottom."""
    if not root:
        return []
    result: list[int] = []
    queue: deque[TreeNode] = deque([root])
    while queue:
        size = len(queue)
        for i in range(size):
            node = queue.popleft()
            if i == size - 1:              # last node of this level
                result.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
    return result

Complexity

• Time: O(n) — full traversal, constant extra work per node
• Space: O(w) — one level in the queue

Interview Tips and Follow-Ups

• Volunteer the deep-left-subtree case ([1, 2, 3, 4]) before being handed it — it is the entire reason this question exists.
• Left side view is i == 0; boundary view (both sides) is a small merge. The family costs nothing once this is down.
• If asked for the DFS version, the invariant is 'first node seen at each depth, right child first' — one queue swap from the left view.

More Tree BFS problems — and the other eight patterns — live in the Technical Interview category. Drill the pattern, not the problem: that is the entire thesis of this series.