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.

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)

Perform level-order BFS. For each level, the rightmost node is the last node in that level's traversal.

Invariant: the queue contains nodes for the current level in left-to-right order.

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

• Invariant: the queue contains nodes for the current level in left-to-right order.
• The queue holds exactly the current level’s nodes before each level pass.
• Processing size nodes and enqueueing children builds the next level correctly.
• Collected level results therefore match the required traversal.

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.

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.