Binary Tree Right Side View

Given the root of a binary tree, return the values of the nodes you can see from the right side, ordered from top to bottom.

Why this is worth learning

The visible node at a depth is the rightmost existing node there, which may come from a left subtree when the right subtree is shallower.

Before coding: one-minute experiment

A root has left child 2 with right child 5, and right child 3 with no children. What is the right-side view?

Function signature

func RightSideView(root *TreeNode) []int

Inputs / outputs

• root: root of the tree.
• Return: slice of visible node values.

Example

    1
   / \
  2   3
   \   \
    5   4
Output: [1,3,4]

Constraints

• 0 <= number of nodes <= 100_000

Core idea (near-solution)

Following Right pointers is a tempting shortcut, but a deeper visible node can come from a left subtree when no right-subtree node exists at that depth. The task selects the rightmost existing node per depth. A full level-order traversal already exposes that order; keep only the last value from each frozen level instead of storing its entire value slice. A right-first DFS with first-seen depth is another valid representation. The queue reference uses left-to-right discovery, so “last” has a precise meaning.

Invariant: At the start of an outer round, the queue contains the current level in left-to-right order; its last removed node is the rightmost at that depth.

Algorithm (step-by-step)

1. If root is nil, return empty.
2. Push root into a queue.
3. While the queue is not empty:
   • Record the current level size n.
   • Pop n nodes; for each, enqueue its children in left-then-right order.
   • The value of the last popped node is the right-side view for this level.
4. Append that value to the result.

Correctness sketch

BFS processes nodes at each depth in left-to-right order. Therefore the final node among the frozen current-level count is precisely the rightmost existing node at that depth. Recording its value yields the visible value for that level. Appending children left before right preserves this ordering at the next depth. Repeating until the queue is empty visits all levels, including deeper levels where only a left-side branch survives. The algorithm does not assume that following root.Right repeatedly reaches every visible node.

Trace (hand walkthrough)

Example input:
    1
   / \
  2   3
   \   \
    5   4
Output: [1,3,4]

Walk:
- level 0: [1] -> rightmost 1
- level 1: [2,3] -> rightmost 3
- level 2: [5,4] -> rightmost 4

Pitfalls to avoid

• Taking the first node of each level instead of the last.
• Changing enqueue order and accidentally picking the wrong node.

Debugging lens

Test a deeper left branch and missing right children. A routine that simply follows Right pointers is not a right-side-view algorithm.

Complexity

• Time: O(n)
• Extra space: O(n) for the queue.

Implementation notes (Go)

• Capture level size; the last node processed per level is the rightmost.
• Enqueue left then right so the final node is the rightmost.

Reconstruction checkpoint

Root 8 has left child 4 and right child 12. Node 4 has right child 6, and 6 has left child 5; node 12 is a leaf. Give the visible sequence and explain why following Right pointers fails.

Return to Binary Tree BFS · Module quiz