4.14.9 — Binary Tree Right Side View

LeetCode 199 · Medium · ★ Blind 75

The problem

Standing to the right of the tree, list the nodes you can see, top to bottom.

   1            visible: 1, 3, 4
 /   \
2     3
 \
  4

Note that 4 is visible even though it is on the left branch — nothing on the right side of the tree reaches that depth, so 4 is the rightmost node at its level.

The pattern

"The rightmost node at each level" is the definition, so this is 4.14.8 with one line changed: instead of collecting every value in a level, keep only the last one.

The solution

Python

from collections import deque

class Solution:
    def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
        if not root:
            return []

        result = []
        queue = deque([root])

        while queue:
            size = len(queue)
            for i in range(size):
                node = queue.popleft()
                if i == size - 1:              # the 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

TypeScript

function rightSideView(root: TreeNode | null): number[] {
  if (!root) return [];

  const result: number[] = [];
  let queue: TreeNode[] = [root];

  while (queue.length) {
    result.push(queue[queue.length - 1].val);   // last of this level
    const next: TreeNode[] = [];
    for (const node of queue) {
      if (node.left) next.push(node.left);
      if (node.right) next.push(node.right);
    }
    queue = next;
  }

  return result;
}

size must be captured before the inner loop, exactly as in 4.14.8 — children added during the round would otherwise change len(queue) mid-loop and the comparison i == size - 1 would fire at the wrong moment.

Children are still enqueued left before right, even though you only want the rightmost. The order matters because it determines which node ends up last.

The DFS version

Walk depth-first, visiting the right child first, and record a value the first time you reach each new depth.

def rightSideView(self, root):
    result = []
    def dfs(node, depth):
        if not node:
            return
        if depth == len(result):        # first node seen at this depth
            result.append(node.val)     # and we came from the right, so it is rightmost
        dfs(node.right, depth + 1)      # right FIRST
        dfs(node.left, depth + 1)
    dfs(root, 0)
    return result

depth == len(result) means no node at this depth has been recorded yet. Since the right subtree is explored first, the first arrival at any depth is the rightmost node there.

It uses O(h) space instead of O(w), so on a balanced tree it is the cheaper version. Swap the two recursive calls and you get the left side view, which is a good check that you understood why the order matters.

Complexity

O(n) time either way. O(w) space for BFS, O(h) for DFS.

Where this goes next

Same BFS skeleton, different line inside the level loop:

• Average of Levels — sum the level and divide.
• Largest Value in Each Row — take the maximum.
• Zigzag Level Order — reverse alternate levels.
• Find Bottom Left Tree Value — the first node of the last level. Easiest as BFS pushing right before left, then taking the final node processed.

The rule: BFS with a frozen level length gives you every "per level" question. Only the line inside the loop changes.

What the interviewer will push on

"Why is 4 visible in the example?" It is the rightmost node at its depth. The view is per level, not per branch.

"Do it depth-first." Right child first, record on first arrival at a depth.

"How would you get the left side view?" Swap the two recursive calls, or take the first node of each level in BFS.

One thing to volunteer: say that this is the level-order template with one line changed. Recognising a problem as a variant, out loud, is worth as much as solving it.

Next: 4.14.10 Count Good Nodes in Binary Tree — information flowing down the tree instead of up.