Binary Tree Right Side View

Difficulty: Medium Source: NeetCode

Problem

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]

Example 3: Input: root = [] Output: []

Constraints:

• The number of nodes in the tree is in the range [0, 100]
• -100 <= Node.val <= 100

Prerequisites

Before attempting this problem, you should be comfortable with:

• BFS / Level Order Traversal — Processing nodes level by level
• DFS with Depth Tracking — Visiting the right side first to see the first node at each depth
• Right Side View Intuition — The rightmost node visible at each level

1. BFS (Last Node Per Level)

Intuition

Level order traversal naturally gives us all nodes at each level in left-to-right order. The rightmost visible node is simply the last node at each level. We collect level order results and pick the last element of each level list.

Algorithm

1. Use BFS with a queue
2. For each level, process all nodes in the queue snapshot
3. Record the last node’s value of each level
4. Return the collected values

Solution

from collections import deque

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def right_side_view_bfs(root):
    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:  # Last node in this level
                result.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)

    return result

# --- helpers ---
def build_tree(values):
    if not values:
        return None
    root = TreeNode(values[0])
    queue = [root]
    i = 1
    while queue and i < len(values):
        node = queue.pop(0)
        if i < len(values) and values[i] is not None:
            node.left = TreeNode(values[i])
            queue.append(node.left)
        i += 1
        if i < len(values) and values[i] is not None:
            node.right = TreeNode(values[i])
            queue.append(node.right)
        i += 1
    return root

# --- tests ---
root1 = build_tree([1, 2, 3, None, 5, None, 4])
print(right_side_view_bfs(root1))  # [1, 3, 4]

root2 = build_tree([1, None, 3])
print(right_side_view_bfs(root2))  # [1, 3]

root3 = build_tree([])
print(right_side_view_bfs(root3))  # []

root4 = build_tree([1, 2])
print(right_side_view_bfs(root4))  # [1, 2]  (only left child exists)

Complexity

• Time: O(n) — every node processed once
• Space: O(w) — queue holds at most the widest level

2. DFS (Right-First, Track Depth)

Intuition

In DFS, if we visit the right child before the left child, then the first time we reach a new depth, that node is the rightmost node visible at that depth. We track which depths we’ve already added to the result.

Algorithm

1. DFS with depth parameter, starting at 0
2. If depth == len(result), this is the first (rightmost) node at this depth — add it
3. Recurse right first, then left

Solution

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def right_side_view_dfs(root):
    result = []

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

    dfs(root, 0)
    return result

# --- helpers ---
def build_tree(values):
    if not values:
        return None
    root = TreeNode(values[0])
    queue = [root]
    i = 1
    while queue and i < len(values):
        node = queue.pop(0)
        if i < len(values) and values[i] is not None:
            node.left = TreeNode(values[i])
            queue.append(node.left)
        i += 1
        if i < len(values) and values[i] is not None:
            node.right = TreeNode(values[i])
            queue.append(node.right)
        i += 1
    return root

# --- tests ---
root1 = build_tree([1, 2, 3, None, 5, None, 4])
print(right_side_view_dfs(root1))  # [1, 3, 4]

root2 = build_tree([1, 2])
print(right_side_view_dfs(root2))  # [1, 2]

root3 = build_tree([1, None, 3])
print(right_side_view_dfs(root3))  # [1, 3]

Complexity

• Time: O(n) — every node visited once
• Space: O(h) — recursion stack depth

Common Pitfalls

Assuming rightmost always means the right child. A node on the left subtree can be the rightmost visible node at its depth if the right subtree doesn’t extend that far. The example [1,2,3,null,5,null,4] shows this — node 4 is a right child of node 3, while node 5 is left child of node 2, both at depth 2, but 4 wins.

Visiting left before right in the DFS approach. If you visit left first, the first node at each depth will be the leftmost, not the rightmost. For right side view, always go right first in DFS.