Definition
- Right side view – the set of nodes visible when standing on the right side of a binary tree, which is the last node per level top to bottom.
- BFS with level-size snapshot – capture
queue.size()at the start of each level, drain that many nodes, and record the one at indexlevelSize - 1. - Not the right spine – the rightmost node per level may come from the left subtree if the right side is shorter.
- Complexity – O(n) time (each node enqueued and dequeued once), O(w) space for the queue.
- DFS alternative – visit right child first, record the first node seen at each new depth.
Imagine standing to the right of the National Bank of India's approval hierarchy and seeing only the person furthest to the right on each rank. The top manager is visible, then on the next rank only the rightmost report is visible because the others are hidden behind them, and so on down the chart.
Understanding the Concepts
What is the right side view of a binary tree?
The right side view is what you would see if you stood on the right side of the tree and looked at it level by level. For each level, only the rightmost node is visible. This is exactly the last node processed in each level of a breadth-first traversal.
package com.bank.model;
public class ApproverNode {
public String name;
public int rank;
public ApproverNode left;
public ApproverNode right;
public ApproverNode(String name, int rank) {
this.name = name;
this.rank = rank;
}
}
How does the BFS level-size snapshot approach work?
Enqueue the root. Loop while the queue is not empty. At the start of each iteration, snapshot the queue size. Drain that many nodes, enqueuing children left then right. The last node drained in each level (index == levelSize - 1) is the rightmost and goes into the result.
package com.bank.service;
import com.bank.model.ApproverNode;
import java.util.*;
public class RightSideView {
public static List<String> rightView(ApproverNode root) {
List<String> result = new ArrayList<>();
if (root == null) return result;
Queue<ApproverNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
int levelSize = queue.size();
for (int i = 0; i < levelSize; i++) {
ApproverNode node = queue.poll();
if (i == levelSize - 1) {
result.add(node.name); // rightmost of this level
}
if (node.left != null) queue.offer(node.left);
if (node.right != null) queue.offer(node.right);
}
}
return result;
}
public static void main(String[] args) {
// CEO
// / \
// VP1 VP2
// /
// DIR1
ApproverNode ceo = new ApproverNode("CEO", 1);
ApproverNode vp1 = new ApproverNode("VP1", 2);
ApproverNode vp2 = new ApproverNode("VP2", 2);
ApproverNode dir1 = new ApproverNode("DIR1", 3);
ceo.left = vp1; ceo.right = vp2;
vp1.left = dir1;
System.out.println("Right view: " + rightView(ceo));
}
}
Right view: [CEO, VP2, DIR1]
Why is the right view not simply the right spine?
A left node can be the rightmost at its level if the right subtree does not extend that deep. In the example above, DIR1 is a left child of VP1, but it appears in the right view because level 3 has no right-side node. Naively following only right children would miss it.
// WRONG: following right children only
List<String> naiveRightView(ApproverNode root) {
List<String> result = new ArrayList<>();
ApproverNode node = root;
while (node != null) {
result.add(node.name);
node = node.right; // misses left-side nodes at deeper levels!
}
return result;
}
// Returns [CEO, VP2] but misses DIR1 at level 3
How does the DFS alternative work?
Visit the right child before the left child, carrying the current depth. The first node seen at each new depth is the rightmost for that level.
public static List<String> rightViewDFS(ApproverNode root) {
List<String> result = new ArrayList<>();
dfs(root, 0, result);
return result;
}
private static void dfs(ApproverNode node, int depth, List<String> result) {
if (node == null) return;
if (depth == result.size()) {
result.add(node.name); // first node at this depth = rightmost
}
dfs(node.right, depth + 1, result); // right first!
dfs(node.left, depth + 1, result);
}
What is the symmetric left view?
The left view captures the first node of each level instead of the last. The only change is i == 0 instead of i == levelSize - 1, or in the DFS version, visiting left before right.
// Left view: change condition from last to first
if (i == 0) {
result.add(node.name); // leftmost of this level
}
What are the edge cases?
Empty tree, single node, and a completely skewed tree (all left children or all right children).
package com.bank.service;
import com.bank.model.ApproverNode;
public class RightViewEdgeCases {
public static void main(String[] args) {
// Empty
System.out.println("Empty: " + RightSideView.rightView(null));
// Single
System.out.println("Single: " + RightSideView.rightView(new ApproverNode("CEO", 1)));
// Left-skewed
ApproverNode skewed = new ApproverNode("CEO", 1);
skewed.left = new ApproverNode("VP", 2);
skewed.left.left = new ApproverNode("DIR", 3);
System.out.println("Left-skewed: " + RightSideView.rightView(skewed));
}
}
Empty: []
Single: [CEO]
Left-skewed: [CEO, VP, DIR]
What is the time and space complexity?
Each node is enqueued and dequeued once, so time is O(n). The queue holds at most one full level, so space is O(w) where w is the maximum width. For a balanced tree, w can be up to n/2 at the last level.
| Approach | Time | Space |
|---|---|---|
| BFS level-size | O(n) | O(w) |
| DFS right-first | O(n) | O(h) |
The DFS version uses less memory on wide, shallow trees because its space is proportional to the height rather than the width.
What should a senior engineer know?
The right view, left view, level averages, zigzag traversal, and level-order traversal are all variations of the same BFS level-size snapshot pattern. Recognizing this family saves time in interviews because the core code is nearly identical across all variants.
In production at National Bank of India, the right view builds an emergency contact sheet showing the most senior fallback contact at each escalation level, and it correctly includes left-side fallbacks when the right branch does not extend deep enough.
// All BFS level variants share this skeleton
while (!queue.isEmpty()) {
int levelSize = queue.size();
for (int i = 0; i < levelSize; i++) {
Node node = queue.poll();
// Variant-specific logic here:
// Right view: capture at i == levelSize-1
// Left view: capture at i == 0
// Averages: accumulate sum, divide by levelSize
// Zigzag: add to front or back depending on level parity
enqueueChildren(node, queue);
}
}
Visual Overview
BFS Level-Size Snapshot
CEO Level 0: [CEO] → right view: CEO
/ \
VP1 VP2 Level 1: [VP1, VP2] → right view: VP2
/
DIR1 Level 2: [DIR1] → right view: DIR1
Right view: [CEO, VP2, DIR1]
Note: DIR1 is a left child but visible from the right
DFS Right-First Alternative
Visit order: CEO(depth 0) → VP2(depth 1) → VP1(depth 1, skip)
→ DIR1(depth 2)
result.size() at each new depth:
depth 0: size=0, add CEO → [CEO]
depth 1: size=1, add VP2 → [CEO, VP2]
depth 1: size=2, skip VP1 (already have depth 1)
depth 2: size=2, add DIR1 → [CEO, VP2, DIR1]
Key Takeaway
The right side view of a binary tree is the last node of each level, which is what you would see standing on the right side. You compute it with BFS and the level-size snapshot: enqueue the root, snapshot the queue size at the start of each level, drain that many nodes, and capture the one at index levelSize - 1. Children are enqueued left then right so nodes process in the correct order.
The crucial subtlety is that the right view is not the right spine. A left node can appear in the view if the right subtree does not extend to that depth. Tracking the last node per level handles this automatically, while naively following only right children would miss deeper left-side nodes.
The DFS alternative visits the right child first and records the first node seen at each new depth. It uses less memory on wide trees because its space is proportional to height rather than width. The symmetric left view captures the first node per level instead of the last.
In our banking system at National Bank of India, the right view builds an emergency contact sheet showing the most senior fallback at each escalation level. Some levels have a missing right branch, so the visible contact is a left-side node, and the level-based last-node rule correctly includes those fallbacks.
Remember one sentence: BFS level-size snapshot capturing the last node per level gives the right view, which is not just the right spine.
---