Binary Tree Right Side View
Binary Tree Right Side View: return the values visible from the right side — the last node of each level.
- The number of nodes in the tree is in the range [0, 100].
- -100 <= Node.val <= 100
Intuition
The binary tree right side view is the list of nodes you would see standing to the right of it — one node per level, the rightmost one on each. The name misleads people into thinking the answer is the path down the right edge, following right children all the way. That is wrong whenever the right subtree is shorter than the left: the deepest levels are then visible only through nodes on the left side of the tree. The correct framing is per level rather than per branch. For every depth, exactly one node is visible — whichever sits furthest right at that depth, no matter which branch it descends from. Once stated that way, two natural implementations appear. The breadth-first version processes the tree level by level and keeps the last node dequeued in each round, which is by construction the rightmost. It is the more obvious of the two and maps directly onto the restatement above. The depth-first version is subtler and shorter. Traverse right child before left, carrying the current depth. The first node you ever reach at a given depth must be the rightmost one there, because the right-first order means everything further right at that depth was already visited. So compare the depth against the number of values collected so far — if they match, this is a depth you have not recorded yet, and this node is the one that is visible.
Level-order with a queue is the obvious route, but DFS works too if you visit the right child first: then the first node reached at each depth is the rightmost one. Comparing depth == len(view) is a neat way to ask "is this the first time I've been this deep?" without tracking levels explicitly.
Approach
Before reading on: price up what the direct approach costs here, then ask what each node needs from its children before it can answer. Aim for O(n) time and O(h) space.
Restate the goal as one node per level
The answer holds exactly one value per depth: the rightmost node at that depth. It is not the chain of right children — when the left subtree runs deeper, its nodes become visible at the levels the right subtree never reaches. Getting this framing right is most of the problem.
BFS version: snapshot the level size
Seed a queue with the root. Each round, record size = len(queue) and dequeue that many nodes, enqueuing children as you go. Taking the size before the inner loop is what keeps levels from bleeding into each other.
BFS version: keep the last node of each round
Within a level, the final node you dequeue is the rightmost at that depth, because you enqueued left children before right ones throughout. Append its value once the inner loop ends — one value per round gives exactly one per level.
DFS version: visit right before left
Recurse with (node, depth), descending into node.right before node.left. This ordering guarantees that the first node reached at any depth is the rightmost one there, which is what makes the next step's test valid.
DFS version: record on first arrival at a depth
If depth == len(view), no node has been recorded at this depth yet, so this one is visible — append it. Every later node at that depth fails the test and is correctly ignored. The list length doubles as a record of which depths are already covered, so no extra set is needed.
Choose based on the shape of the tree
BFS uses O(w) space for the queue, where w is the widest level — up to n/2 on a complete tree. DFS uses O(h) stack space, which is O(log n) when balanced. DFS is the better choice on wide trees; BFS is safer on deep, skewed ones where recursion could overflow the stack.
Cost of either version
Both visit every node exactly once for O(n) time, since a node's visibility cannot be determined without looking at it. They differ only in space, and in how directly the code mirrors the one-node-per-level restatement.
Solution & live demo
Common pitfalls
Recursing left before right
dfs(node.left, depth + 1) dfs(node.right, depth + 1)
dfs(node.right, depth + 1) dfs(node.left, depth + 1)
The whole method rests on the first arrival at each depth being the rightmost node. Going left first records the left side view instead — the code looks right and the answer is silently mirrored.
Overwriting the stored value at each depth
if depth < len(view):
view[depth] = node.val
else:
view.append(node.val)if depth == len(view):
view.append(node.val)With right-first ordering the first node seen at a depth is already the correct one, so later nodes at that depth must be ignored. Overwriting replaces it with a node further left.
Tracking depth with a shared mutable counter
self.depth += 1 dfs(node.right) self.depth -= 1
dfs(node.right, depth + 1)
It's an extra pair of mutations to keep balanced across every branch and early return. Depth is naturally per-path, so it belongs in the call argument where the language unwinds it for you.
Edge cases
A left node can be visible if the right subtree is shallower — level-based logic handles it (unlike 'just walk right').
[].