Binary Tree Right Side View: The Right-First BFS Trick
Solve Binary Tree Right Side View with a level-order BFS that enqueues right children first — intuition, JavaScript code, a worked walkthrough, and complexity.
This article has an interactive companion
Don't just read it — step through it interactively, one state change at a time.
Stand to the right of a binary tree and look left. Some nodes block others; you only see the outermost node at each depth. That silhouette — one node per level, top to bottom — is the right side view.
The naive instinct is to hunt for "the last node on each row." But there's a cleaner reframe the moment you reach for a queue: if you process each level right-to-left, the node you see is simply the first one you pop. No tracking "last," no comparing positions — the first pop wins.
That one ordering decision turns a fiddly problem into eight lines.
The problem
Given the root of a binary tree, return the values of the nodes you can see, ordered top to bottom, when the tree is viewed from the right side.
Input: root = [1, 2, 3, null, 5, null, 4]
1 <- see 1
/ \
2 3 <- see 3 (blocks 2)
\ \
5 4 <- see 4 (blocks 5)
Output: [1, 3, 4]The array is level-order: 1 is the root, 2 and 3 are its children, 5 is the right child of 2, and 4 is the right child of 3. From the right, depth 0 shows 1, depth 1 shows 3 (the rightmost), and depth 2 shows 4. Node 5 is hidden behind 4 even though it sits to the left — visibility is per-depth, not per-subtree.
Two things fall out of that statement:
- The answer has exactly one value per level — so its length equals the tree's height.
- "Rightmost" is decided within a level, not within a parent. A deep left subtree can still be invisible if a shorter right subtree covers its depth.
The brute force baseline
The literal reading — "find the rightmost node at each depth" — leads to probing the tree once per level:
function rightSideView(root) {
const result = [];
const height = maxDepth(root);
for (let depth = 0; depth < height; depth++) {
result.push(rightmostAtDepth(root, depth));
}
return result;
}
function rightmostAtDepth(node, depth) {
if (!node) return null;
if (depth === 0) return node.val;
// try the right subtree first; fall back to the left
const right = rightmostAtDepth(node.right, depth - 1);
return right !== null ? right : rightmostAtDepth(node.left, depth - 1);
}It works, but it re-walks the tree from the root for every depth. On a skewed tree of height n, that's n traversals of up to n nodes — O(n²). You're paying to re-descend past the same upper nodes over and over just to reach one new level. A single sweep should be enough.
The key insight: enqueue right before left
Breadth-first search already visits a tree level by level using a queue. The usual trick for "the last node per level" is to count levelSize at the top of each level and grab the node when the counter hits the end.
The visualizer teaches a sharper move. Instead of chasing the last node, flip the enqueue order: push the right child before the left child. Now every level enters the queue right-to-left, so the very first node you dequeue at each level is the rightmost one. Capture it, ignore the rest, done.
You still process all levelSize nodes at each depth — you need them to seed the next level — but the only one you record is the one at position i === 0.
The optimal solution
function rightSideView(root) {
if (!root) return [];
const result = [];
const queue = [root];
while (queue.length > 0) {
const levelSize = queue.length;
for (let i = 0; i < levelSize; i++) {
const node = queue.shift();
if (i === 0) {
result.push(node.val);
}
if (node.right) queue.push(node.right);
if (node.left) queue.push(node.left);
}
}
return result;
}Three details carry the whole thing:
levelSize = queue.lengthis snapshotted before the inner loop. The queue grows as you enqueue children, so freezing the count is what keeps one level's work separate from the next.i === 0is the capture. Because right children go in first, position 0 is guaranteed to be the rightmost visible node — no scanning to find "last."node.rightthennode.leftis the ordering that makes all of this true. Swap those two lines and you get the left side view instead.
Walkthrough: root = [1, 2, 3, null, 5, null, 4]
Tracing the queue as [values] and recording only the first pop per level:
| Step | Level | levelSize | i | Dequeued | i === 0? | Enqueue (right, left) | queue after | result |
|---|---|---|---|---|---|---|---|---|
| 1 | 0 | 1 | 0 | 1 | yes → record | 3, 2 | [3, 2] | [1] |
| 2 | 1 | 2 | 0 | 3 | yes → record | 4 | [2, 4] | [1, 3] |
| 3 | 1 | 2 | 1 | 2 | no | 5 | [4, 5] | [1, 3] |
| 4 | 2 | 2 | 0 | 4 | yes → record | — | [5] | [1, 3, 4] |
| 5 | 2 | 2 | 1 | 5 | no | — | [] | [1, 3, 4] |
Watch step 2 and step 3. At level 1, 3 pops first (it was enqueued before 2 back in step 1), gets recorded, and its right child 4 goes in. Then 2 pops, is skipped, and its right child 5 is enqueued after 4. That ordering is why, at level 2, 4 pops before 5 and becomes the visible node — even though 5 is 2's child and 2 came first in the input. The queue is empty after step 5, so the loop ends with [1, 3, 4].
Complexity
| Approach | Time | Space | Why |
|---|---|---|---|
| Per-depth probe | O(n²) | O(h) | re-traverses from the root once per level |
| Right-first BFS | O(n) | O(w) | each node dequeued and enqueued exactly once |
Every node enters and leaves the queue a single time, so the BFS is linear in the node count n. Space is bounded by the widest level w — the maximum number of nodes the queue holds at once, which is O(n) for a nearly complete tree and O(1) for a skewed one. That's a full order of magnitude better than re-probing per depth.
Common mistakes
- Enqueuing left before right and still capturing
i === 0. That records the leftmost node per level — the left side view. Keepnode.rightfirst, or switch to capturingi === levelSize - 1if you insist on left-first order. - Reading
queue.lengthinside the loop condition. You must freezelevelSizebefore the inner loop; the queue length changes as children are pushed, and a live read bleeds the next level into the current one. - Forgetting the empty-tree guard.
if (!root) return []up front; otherwise[root]seeds the queue withundefinedand the firstshift()explodes. - Assuming the deepest node is always visible. A long left subtree can be fully hidden if a right subtree reaches the same depth. Visibility is per-level, decided by BFS order — not by which subtree is taller.
Where this pattern shows up next
Once "snapshot levelSize, then loop the level" clicks, a whole family of level-order problems opens up:
- Binary Tree Zigzag Level Order Traversal — same level loop, but you flip direction each row instead of keeping one node.
- Maximum Depth of Binary Tree — count the levels the BFS produces rather than reading a node from each.
- Maximum Depth of Binary Tree - Top Down — the DFS counterpart that threads depth down the recursion.
- Balanced Binary Tree — depth per subtree, checked bottom-up for a balance guarantee.
You can also step through the right side view interactively and watch the queue fill right-to-left while the first pop of each level lights up.
FAQ
Why enqueue the right child before the left child?
Because it makes the rightmost node at each level the first one you dequeue. In standard BFS you'd count to the last node of the level to find the visible one; enqueuing right-first inverts the queue order so position i === 0 is already the answer. It removes the bookkeeping of tracking "last" entirely — you capture on the first pop and skip everything after.
What is the time and space complexity?
Time is O(n), where n is the number of nodes, because BFS dequeues and enqueues each node exactly once. Space is O(w), where w is the maximum width of the tree — the most nodes the queue holds at any moment. For a nearly complete tree that's roughly n/2 nodes (O(n)); for a skewed, list-like tree it's O(1). The naive per-depth probe, by contrast, is O(n²) time because it restarts from the root for every level.
Can I solve the right side view with DFS instead of BFS?
Yes. Do a depth-first traversal that visits the right child before the left, and pass the current depth down. The first time you reach a new depth, that node is the rightmost visible one — record it. Track the number of levels already captured and append only when depth === result.length. It's O(n) time and O(h) space for the recursion stack, and it's a clean alternative when you'd rather not manage an explicit queue.
Does an empty tree or a single node work?
Both are handled. An empty tree (root === null) returns [] from the up-front guard. A single node returns [root.val]: the queue starts with one node, levelSize is 1, the lone node pops at i === 0 and is recorded, and with no children the queue empties and the loop ends. No edge-case branching beyond the initial null check is needed.
Make it stick: run this one yourself
Don't just read it — step through it interactively, one state change at a time.