Binary Tree Right Side View

Problem Statement

Given the root of a binary tree, imagine yourself standing on the right side of it. Return the values of the nodes you can see ordered from top to bottom.

Examples

Example 1

Input: root = [1,2,3,null,5,null,4]
Output: [1,3,4]

Tree (view from right):
    1       ← see 1
   / \
  2   3     ← see 3 (rightmost)
   \   \
    5   4   ← see 4 (rightmost)

Example 2

Input: root = [1,2,3,4,null,null,null,5]
Output: [1,3,4,5]

Tree:
       1     ← see 1
      / \
     2   3   ← see 3
    /
   4         ← see 4 (only node at level 2)
  /
 5           ← see 5

Example 3

Input: root = [1,null,3]
Output: [1,3]

Example 4

Input: root = []
Output: []

Intuition

From the right side, we see the rightmost node at each level.

Two approaches:

1. BFS (Level Order): Process level by level, take last node of each level
2. DFS (Right-first): Visit right children first, take first node at each depth

Both work, but BFS is more intuitive for "level" problems.

Pattern Recognition

This is a BFS Level Processing problem with:

• Level-by-level traversal
• Extract rightmost node per level
• Similar to Level Order Traversal

Approach

BFS with Queue (Recommended)

1. Initialize: queue with root, result list
2. For each level:
   • Get level size
   • Process all nodes in level
   • Key: The last node processed at each level is the rightmost
   • Add last node's value to result
3. Return result

DFS Right-First (Alternative)

Visit right child before left:

def dfs(node, depth):
  if not node: return
  if depth == len(result):  # First node at this depth
    result.append(node.val)
  dfs(node.right, depth + 1)  # Right first!
  dfs(node.left, depth + 1)

This works because we visit right child first, so the first node we see at each depth is the rightmost.

Edge Cases

• Empty tree
• Single node
• Only left children (right side view still shows leftmost at deeper levels)
• Only right children
• Zigzag tree

Complexity Analysis

BFS Approach

• Time: O(n) where n = number of nodes

  • Visit each node once
  • O(1) work per node

• Space: O(w) where w = maximum width

  • Queue holds one level at a time
  • O(n) worst case for complete tree

DFS Approach

• Time: O(n)
• Space: O(h) where h = height
  • Recursion stack
  • O(log n) balanced, O(n) skewed