Binary Tree Right Side View
Picture a binary tree drawn top-down and imagine standing to its right, looking left. On every level you can only see the node that is furthest to the right; everything else on that level is hidden behind it.
Given the root of the tree, return the values you can see, ordered from the top level to the bottom level. Note that the visible node on a level is not always a right child: if a level’s right side is empty, a node from the left side becomes visible.
The tree is given as a level-order array with null for missing children; an empty array means an empty tree.
Example 1
Example 2
Example 3
Constraints
0 <= number of nodes <= 100-100 <= Node.val <= 100
Pattern Path · Trees: BFS · problem 93 of 169
Start simple
Collect every level into its own list with BFS and take the last element of each list: O(n) time, O(n) space; already optimal, just a little wasteful.
The key idea
The visible node on each level is simply the last node of that level in left-to-right order. A breadth-first search naturally walks the tree level by level, so the task reduces to knowing where each level ends.
Start a queue with the root. At the beginning of every round, the queue holds exactly one complete level, so record its length k and pop exactly k nodes, pushing their children (left before right) for the next round. The k-th node popped is the rightmost node of the level: append its value.
This handles the tricky shape where the right side of a level is empty: the rightmost node of that level then sits in a left subtree, and BFS still finds it because it is the last node on that level regardless of which branch it came from.
An equally good DFS variant visits the right child before the left, carrying the depth; the first node reached at each new depth is the visible one.
Complexity
- Time:
O(n) - Space:
O(w), w = maximum width of the tree
Python
from collections import deque
class Solution:
def rightSideView(self, root):
if root is None:
return []
view = []
queue = deque([root])
while queue:
level_size = len(queue) # the queue holds exactly one level
for i in range(level_size):
node = queue.popleft()
if i == level_size - 1: # last node of this level is visible
view.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
return viewJavaScript
var rightSideView = function(root) {
if (root === null) return [];
const view = [];
let level = [root];
while (level.length > 0) {
view.push(level[level.length - 1].val); // last node of this level is visible
const next = [];
for (const node of level) {
if (node.left) next.push(node.left);
if (node.right) next.push(node.right);
}
level = next;
}
return view;
};What the interviewer is checking
It checks whether you can do level-order traversal with clean level boundaries, and whether you spot the case where the visible node comes from a left subtree.
Mistakes to avoid
- Only following right children, which misses levels where the right side is empty.
- Mixing levels together by not fixing the level size before popping.
- Not handling an empty tree.
Follow-ups to expect
- Return the left side view instead. (Keep the first node of each level.)
- Return the top view or bottom view. (Track horizontal distance per node.)
- Can you do it without a queue? (DFS right-first with depth.)
In real software
Level-by-level traversal is how UI layout engines and org-chart tools reason about tree rows, and keeping the last item per level mirrors rendering only the visible edge of a hierarchy.