Binary Tree Right Side View

You're given the root of a binary tree. Picture standing to the right of the tree and looking left: on each level you can see only one node, the one furthest to the right.

Return the values of those visible nodes, ordered from the top level to the bottom. A node on a deeper level can be visible even if it hangs off a left branch, as long as nothing on its level is further right.

The tree is given in level order, with null marking a missing child. An empty tree has no visible nodes.

The tempting shortcut is "keep walking right from the root", but that misses nodes like the 2 in [7, 3, 9, 2], which sit on a left branch once the right side runs out.

The real definition is per level: for each depth, which node is furthest right? A breadth-first search that processes one level at a time gives you each level as a group, and the last node in that group is the answer for that depth.

A depth-first search works too: visit the right child before the left, and the first node you reach at each new depth is the visible one.

from collections import deque


def right_side_view(root: Optional[TreeNode]) -> list[int]:
    if not root:
        return []
    view = []
    queue = deque([root])
    while queue:
        for _ in range(len(queue)):  # one level
            node = queue.popleft()
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        view.append(node.val)  # last node popped on this level
    return view

function rightSideView(root) {
  if (!root) return [];
  const view = [];
  let level = [root];
  while (level.length) {
    view.push(level[level.length - 1].val); // rightmost on this level
    const next = [];
    for (const node of level) {
      if (node.left) next.push(node.left);
      if (node.right) next.push(node.right);
    }
    level = next;
  }
  return view;
}

Start by stating the trap: "it is not just the right spine; a left node is visible when its level has nothing further right." Drawing [7, 3, 9, 2] makes that concrete and shows the interviewer you checked the definition before coding.

Then pick BFS by level and say how you separate levels (snapshot the queue length). Offering the right-first DFS as an alternative, with its O(h) space trade-off, is a good sign that you know both traversals.