Trees crash course ↗ · 145

199. Binary Tree Right Side View

Imagine standing to the right of a binary tree and looking left — you see exactly one node per level: the rightmost one. BFS with a level-width snapshot makes it trivial: process each level, grab the last node.

● MediumBFS / Level OrderTree TraversalTypeScript

PROBLEM What we're solving

Given the root of a binary tree, return the values visible when viewed from the right side — one value per depth level, the rightmost node at each level.

Concrete example with tree [3, 9, 20, null, null, 15, 7]:

    3        ← only node at depth 0 → see 3
   / \
  9  20      ← rightmost at depth 1 → see 20
    /  \
   15   7    ← rightmost at depth 2 → see 7

Output: [3, 20, 7].

KEY IDEA Snapshot the level width, take the last

Insight → BFS naturally groups nodes by depth. Before each level loop, snapshot levelSize = queue.length. Process exactly that many nodes; the node at index levelSize - 1 is the rightmost visible one. Add it to the result. This is a single O(n) pass — no extra memory beyond the queue.

RECIPE Level-order BFS, one snapshot per level

0 · Edge case. If root is null, return []. An empty tree has no visible nodes.
1 · Initialize. Push root into a queue. This is the BFS frontier for depth 0.
2 · Per-level loop. While the queue is non-empty, read levelSize = queue.length. This freezes the current level's count before we add children.
3 · Drain the level. Dequeue exactly levelSize nodes. For each, push its left and right children (non-null only) for the next level.
4 · Record the last. When i === levelSize - 1, push the node's value to result. That node is rightmost at this depth.
5 · Return. After all levels are drained, result holds one value per depth.

Classic confusion → Many learners reach for DFS and try to record the first node seen at each depth when traversing right-subtree-first. That does work, but the depth-tracking logic is subtle (you must record only the first visit per depth, not overwrite on re-entry). The BFS approach is more direct: the last node dequeued each level is unambiguously the rightmost. If asked for the left side view, just take index 0 instead of levelSize - 1.

COST Complexity & alternatives

DFS (right-first, track depth)

O(n)

Same asymptotic, but depth-tracking is fiddly to get right.

BFS level-order snapshot

O(n)

O(n) time; O(w) space where w is max level width (worst case n/2).

Both solutions are O(n) time. BFS queue holds at most one full level — up to n/2 nodes for a perfect binary tree, so space is O(w). The DFS recursive stack is at most O(h) deep, where h is height — better for wide balanced trees, worse for skewed trees.

Pattern transfer → The "snapshot levelSize then drain exactly that many" idiom solves Binary Tree Level Order Traversal, Maximum Depth of Binary Tree, Minimum Depth of Binary Tree, Rotting Oranges (multi-source BFS on a grid), and Word Ladder (same level = same edit distance).

RUN IT BFS level order — last node per level

Tree (level-order):

step 0 / 9

STARTInitialize BFS queue with root 3. We'll process level by level and record the last node of each level.

1function rightSideView(root: TreeNode | null): number[] {
2  if (!root) return [];
3▶  const result: number[] = [];
4▶  const queue: TreeNode[] = [root];
5 
6  while (queue.length > 0) {
7    const levelSize = queue.length;         // snapshot current level width
8    for (let i = 0; i < levelSize; i++) {
9      const node = queue.shift()!;
10      if (i === levelSize - 1) {            // last node in this level
11        result.push(node.val);
12      }
13      if (node.left)  queue.push(node.left);
14      if (node.right) queue.push(node.right);
15    }
16  }
17  return result;
18}

3queue

State

—

level

[3]

queue

—

levelSize

—

node

[ ]

result

current nodevisited / in queueadded to result

slowfast

TYPESCRIPT The solution, annotated

rightSideView.ts
function rightSideView(root: TreeNode | null): number[] {
  if (!root) return [];
  const result: number[] = [];
  const queue: TreeNode[] = [root];

  while (queue.length > 0) {
    const levelSize = queue.length;         // snapshot current level width
    for (let i = 0; i < levelSize; i++) {
      const node = queue.shift()!;
      if (i === levelSize - 1) {            // last node in this level
        result.push(node.val);
      }
      if (node.left)  queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
  }
  return result;
}

Reading it block by block

Line 2 — null guard. An empty tree has no levels and no visible nodes. Return early before touching the queue.

Lines 3–4 — initialization. result collects one value per level. The queue starts with just the root — the entire first level.

Line 7 — level-width snapshot. Reading queue.length beforethe inner loop is the crux of the pattern. It captures how many nodes are at the current depth so new children pushed inside the loop don't contaminate the count.

Lines 8–14 — drain the level. The inner for loop processes exactly the snapshotted count. At each step we dequeue, optionally record, and enqueue children. When i === levelSize - 1we're at the rightmost node of this level.

Line 17 — return. After the outer while loop empties the queue, every depth has contributed exactly one value to result.

Complexity → O(n) time — each node is enqueued and dequeued exactly once. O(w) space for the queue, where w is the maximum width of any level (up to n/2 for a perfect binary tree). The result array is O(h) where h is tree height.

INTERVIEWFollow-ups they'll ask

"Can you do it with DFS instead?" Yes — traverse right subtree before left, and record a node's value only the first time you reach each depth (use a depth parameter and a map).
"What if you want the left side view?" In BFS, record index 0 instead of levelSize - 1. In DFS, traverse left-first and again record only the first node per depth.
"Return the values at every level (level order traversal)?" Collect all nodes per level into a sub-array: replace if (i === levelSize - 1) result.push(...) with levelArr.push(node.val) and push the sub-array at the end of each level.
"What if the tree is very wide vs. very deep?" BFS queue stores up to O(w) nodes; DFS call stack is O(h). For a balanced tree w ≈ n/2 and h ≈ log n — so DFS uses less space. For a pathological right-skewed tree w = 1 and h = n — BFS uses less.
"Handle nodes visible at each level from both sides?" Take the first and last node per BFS level, and deduplicate when the level has only one node.

OPTIMAL BFS / Level Order

rightSideView.ts
function rightSideView(root: TreeNode | null): number[] {
  if (!root) return [];
  const result: number[] = [];
  const queue: TreeNode[] = [root];

  while (queue.length > 0) {
    const levelSize = queue.length;         // snapshot current level width
    for (let i = 0; i < levelSize; i++) {
      const node = queue.shift()!;
      if (i === levelSize - 1) {            // last node in this level
        result.push(node.val);
      }
      if (node.left)  queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
  }
  return result;
}

ALT 1 Brute force — grab the last node at each depth

O(n²) time · O(h) space

Compute the height, then for each depth d run a DFS that records every node at that depth and keep only the last one visited (the rightmost, since we recurse right before left).

approach-2.ts
function rightSideView(root: TreeNode | null): number[] {
  function height(node: TreeNode | null): number {
    if (node === null) return 0;
    return 1 + Math.max(height(node.left), height(node.right));
  }

  // Visit right subtree first, so the LAST value written for a depth is the rightmost.
  function rightmost(node: TreeNode | null, depth: number, slot: { val: number | null }): void {
    if (node === null) return;
    if (depth === 0) { slot.val = node.val; return; }
    rightmost(node.right, depth - 1, slot);
    rightmost(node.left, depth - 1, slot);
  }

  const result: number[] = [];
  const h = height(root);
  for (let d = 0; d < h; d++) {
    const slot: { val: number | null } = { val: null };
    rightmost(root, d, slot);
    if (slot.val !== null) result.push(slot.val);
  }
  return result;
}

Note → Re-walking the whole tree once per depth is O(n²) on a skewed tree. A single BFS that takes the last node of each level — or a right-first DFS that pushes the first node seen at each new depth — does it in one O(n) pass.

MNEMONIC The one-liner

"Freeze the level size, drain it, grab the tail — that tail is what your eye sees from the right."

TRIGGERS When you see _ → reach for _

"visible from the right/left side"	BFS level-order, last/first per level
process one depth at a time	snapshot levelSize = queue.length before loop
"level order traversal"	BFS with levelSize snapshot, push children
tree problem mentioning depth or layer	BFS queue with per-level loop

SKELETON The reusable shape

skeleton.ts
function rightSideView(root: TreeNode | null): number[] {
  if (!root) return [];
  const result: number[] = [];
  const queue: TreeNode[] = [root];

  while (queue.length > 0) {
    const levelSize = queue.length;
    for (let i = 0; i < levelSize; i++) {
      const node = queue.shift()!;
      if (i === levelSize - 1) result.push(node.val);
      if (node.left)  queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
  }
  return result;
}

FLASHCARDS Tap to flip

What does "right side view" mean?

The last (rightmost) node visible at each depth level when the tree is viewed from the right.

tap to flip

1 / 7

Answer to reveal explanations. No penalty for retries.Score: 0 / 9

QUESTION 01

For tree [3, 9, 20, null, null, 15, 7], what does rightSideView return?

QUESTION 02

Why must you snapshot levelSize = queue.length BEFORE the inner loop?

QUESTION 03

What is the time complexity of the BFS right-side-view solution?

QUESTION 04

If you wanted the LEFT side view instead, what is the only change?

QUESTION 05

A right-skewed tree (every node only has a right child) of depth 5 has what right side view?

QUESTION 06

What is the space complexity of the BFS queue in the worst case?

QUESTION 07

In the DFS right-first alternative, when should you record a node?

QUESTION 08

#199 · Binary Tree Right Side ViewBFS level-order traversal: snapshot the queue size at the start of each level and record the last node processed as the rightmost visible node at that depth.Which algorithmic approach does this primarily use?

QUESTION 09

PROBLEM What we're solving

KEY IDEA Snapshot the level width, take the last

RECIPE Level-order BFS, one snapshot per level

COST Complexity & alternatives

RUN IT BFS level order — last node per level

TYPESCRIPT The solution, annotated

Reading it block by block

INTERVIEWFollow-ups they'll ask

OPTIMAL BFS / Level Order

ALT 1 Brute force — grab the last node at each depth

MNEMONIC The one-liner

TRIGGERS When you see ___ → reach for ___

SKELETON The reusable shape

FLASHCARDS Tap to flip

TRIGGERS When you see _ → reach for _