199 - Binary Tree Right Side View

Difficulty: Medium | Pattern: BFS Level Order | Company tags: Facebook, Amazon, Bloomberg, Uber

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.

Example 1:

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

Example 2:

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

Approach: BFS Level Order — O(n)

Key insight: Do BFS level by level. For each level, the last node in the queue is the rightmost visible node. Add it to the result.

from collections import deque

def rightSideView(root) -> list[int]:
    if not root:
        return []
    
    result = []
    queue = deque([root])
    
    while queue:
        level_size = len(queue)
        for i in range(level_size):
            node = queue.popleft()
            if i == level_size - 1:
                result.append(node.val)  # last node in level
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
    
    return result

Approach: DFS (Right-First)

def rightSideView(root) -> list[int]:
    result = []
    
    def dfs(node, depth):
        if not node:
            return
        if depth == len(result):
            result.append(node.val)  # first time at this depth (rightmost so far)
        dfs(node.right, depth + 1)  # visit right FIRST
        dfs(node.left, depth + 1)
    
    dfs(root, 0)
    return result

Dry Run

Tree: [1,2,3,null,5,null,4]

Level 0: [1] → last = 1 → result=[1]
Level 1: [2,3] → last = 3 → result=[1,3]
Level 2: [5,4] → last = 4 → result=[1,3,4]

Output: [1,3,4] ✓

Edge Cases

• Empty tree → return []
• Single node → return [root.val]
• Only left children → see only the leftmost path (same as left side view if mirrored)
• Zigzag tree → captures rightmost at each depth even if it's a left child

Complexity

• Time: O(n) — every node visited once
• Space: O(w) — max width of tree (queue); O(h) for DFS