The O(n) Club: Binary Tree Right Side View—Why Only ‘Right’ Isn’t Always Right
⚡ TL;DR
Fight your right-bias: the goal is to return every level’s rightmost node—AKA the actual visible ones, not just whatever your DFS stumbles into. Go Breadth-First (BFS), collect the last node at each level, and don’t assume the left side is invisible. Quick Java snack:
// Java BFS for right side view public List <integer> rightSideView(TreeNode root) { List <integer> result = new ArrayList<>(); if (root == null) return result; Queue <treenode> queue = new LinkedList<>(); queue.offer(root); while (!queue.isEmpty()) { int size = queue.size(); for (int i = 0; i < size; i++) { TreeNode node = queue.poll(); if (node.left != null) queue.offer(node.left); if (node.right != null) queue.offer(node.right); if (i == size - 1) result.add(node.val); } } return result; } </treenode></integer></integer>
🧠 How Devs Usually Mess This Up
Classic slip-up: traversing only right children. It’s tempting, but you’ll totally miss out when a left child is photobombing deeper than its right sibling. Or maybe you lean hard into right-first DFS—until, whoops, the left branch wins the depth contest and your function skips the visible champ. The tree doesn’t care about your assumptions; it’s all about perspective.
🔍 What’s Actually Going On
Picture a group photo from the very end of the row; you see whomever pokes their head out farthest per row. In a tree, that means for each level, whatever node you process last—after traversing left and right kids—gets seen. BFS is perfect for this: it moves through each level, allowing everyone a fair shot at the limelight, and casually picks the last face peeking out (even if it’s not always Mr. Right).
🛠️ PseudoCode
- If root is null: Return an empty list. Nothing to see here, folks.
- Initialize a queue. Stick the root node in so you have somewhere to begin.
- While the queue’s not empty:
- Get the count of nodes at this level (queue.size())—otherwise, chaos.
- For each node at this level:
- Remove from queue.
- If it has a left child, queue it. If it has a right child, queue that too.
- If this is the last node for this batch, add its value to your answer.
Why does this work? Think of it as snacking your way through tree levels; last bite at each layer is what sticks.
💻 The Code
import java.util.*;
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
public class Solution {
public List
<integer> rightSideView(TreeNode root) {
List
<integer> result = new ArrayList<>();
if (root == null) return result;
Queue
<treenode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll();
if (node.left != null) queue.offer(node.left);
if (node.right != null) queue.offer(node.right);
if (i == size - 1) result.add(node.val);
}
}
return result;
}
}
</treenode></integer></integer>
⚠️ Pitfalls, Traps & Runtime Smacks
- Unbalanced trees: Not all trees live that perfect binary life. Lefty limbs sometimes outstretch the right; test with weird, zig-zaggy trees or the interviewer will.
- Null nodes: Always check before queueing children unless you have a sudden love for NullPointerException.
- Complexity: Time? O(n). Space? O(n). You’re literally touching every node and storing up to an entire level at once. Not magic, just practical.
🧠 Interviewer Brain-Tattoo
“The right view isn’t always who sits right—it’s who peeks out when the crowd gets weird.” Or, in other words: Perspective reveals more than direction ever will.
