Binary Tree Right Side View Solution

Problem

Imagine standing to the right of a binary tree and looking left — which nodes can you see? Return the value of the rightmost visible node at each depth level, from top to bottom. A node is visible if no other node at the same depth is to its right.

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

Input: root = [1, 2, 3, null, 5, null, 4]
Output: [1, 3, 4]
Explanation: At depth 0 you see node 1, at depth 1 node 3 blocks node 2, at depth 2 node 4 blocks node 5.

Counter-example: if node 3 had no right child, node 5 (a left child of node 2) would become the rightmost visible node at depth 2 and appear in the output. Being a left child does not automatically exclude a node.

Intuition

The right side view is exactly the last node at each depth level. A level-order (BFS) traversal naturally groups nodes by depth, so grabbing the final node of each group is straightforward. Alternatively, if you always recurse into the right subtree before the left, the first node you encounter at any new depth is guaranteed to be the rightmost — making a depth-first traversal with a simple guard condition equally effective, and more memory-efficient on balanced trees.

Approach 1 — BFS (Level Order)

Process the tree level by level using a queue. Before entering each level's loop, snapshot the queue size so you know exactly how many nodes belong to this level. The last node processed in that loop is the rightmost visible one.

Return an empty list if the root is null.
Initialize a queue with the root.
While the queue is not empty, record level_size = len(queue).
Dequeue exactly level_size nodes, adding each node's children to the queue.
After the last node of the level, append its value to the result.
Return the result.

1from collections import deque
2
3def rightSideView(root):
4    if not root:
5        return []
6
7    result = []
8    queue = deque([root])
9
10    while queue:
11        level_size = len(queue)  # snapshot before enqueuing next level's children
12
13        for i in range(level_size):
14            node = queue.popleft()
15
16            if i == level_size - 1:  # only the last node in the level is visible from the right
17                result.append(node.val)
18
19            if node.left:
20                queue.append(node.left)
21            if node.right:
22                queue.append(node.right)
23
24    return result

Time: O(n) — every node is visited exactly once.
Space: O(n) — the queue can hold an entire level; the widest level of a complete binary tree contains ⌈n/2⌉ nodes.

Approach 2 — DFS (Right-First Preorder)

Traverse depth-first, always visiting the right child before the left. The first time the recursion reaches a new depth, that node must be the rightmost one at that depth — append it to the result. Subsequent nodes at the same depth are skipped because the result already has an entry there.

Define a helper that takes a node and its current depth.
Base case: return if the node is null.
If depth == len(result), this is the first visit to this depth — append the node's value.
Recurse into the right child first, then the left child.
Call the helper on the root at depth 0.

1def rightSideView(root):
2    result = []
3
4    def dfs(node, depth):
5        if not node:
6            return
7
8        if depth == len(result):  # first node encountered at this depth comes from the right
9            result.append(node.val)
10
11        dfs(node.right, depth + 1)  # right child first so rightmost node wins
12        dfs(node.left, depth + 1)
13
14    dfs(root, 0)
15    return result

Time: O(n) — every node is visited exactly once.
Space: O(h) — the call stack holds at most h frames, where h is the tree height (O(log n) balanced, O(n) worst-case skewed).

Complexity Summary

Approach	Time	Space	When to use
BFS (Level Order)	O(n)	O(n)	When you need explicit level grouping or want to avoid recursion
DFS (Right-First)	O(n)	O(h)	When the tree is roughly balanced and minimizing memory matters

Common Mistakes

Visiting left before right in DFS: The condition depth == len(result) records the first node seen at each depth. Visiting the left subtree first means you record a left-side view instead. The right child must be recursed into first.
Assuming only right children are visible: A left child can be the rightmost node at its depth if its parent has no right child. The algorithm handles this automatically — don't add a special case for it.
Reading queue size inside the level loop: Calling len(queue) or queue.size() inside the loop returns a growing count as children are enqueued, corrupting the level boundary. Snapshot the size before the loop starts.
Starting depth at 1 instead of 0: With the DFS approach, initializing depth = 1 means the root never satisfies depth == len(result) (which starts at 0), so the root's value is silently dropped.
Not handling the empty tree: Both approaches must guard against a null root; the correct return value is an empty list, not a crash.

Binary Tree Right Side View — Solution