Definition
- Right view – the set of nodes visible from the right side of the tree: one per level, the rightmost node.
- Level-size snapshot – capture
queue.size()at each level's start, drain that many nodes, and record the last. - Not the right spine – the rightmost node per level may come from the left subtree if the right subtree is shorter.
- Complexity – O(n) time, O(w) space for BFS; O(n) time, O(h) space for DFS.
- Symmetric – the left view captures the first node per level instead.
Looking at the National Bank of India approval tree from the right edge, you see only the rightmost approver on each rank, because they block the view of everyone to their left on that rank. Collecting the rightmost approver per rank top to bottom is the right view.
Understanding the Concepts
What is the right view of a binary tree?
The right view is the list of nodes visible when standing on the right side of the tree, looking at it level by level from top to bottom. For each level, only the rightmost node is visible. This is defined as the last node processed in each level of a BFS.
package com.bank.model;
public class RankNode {
public String name;
public RankNode left;
public RankNode right;
public RankNode(String name) {
this.name = name;
}
}
How do you compute the right view with BFS?
Enqueue the root. Loop while the queue is not empty. At each iteration, snapshot the level size, drain that many nodes (enqueuing children left then right), and record the last one (index == levelSize - 1).
package com.bank.service;
import com.bank.model.RankNode;
import java.util.*;
public class RightViewBFS {
public static List<String> rightView(RankNode root) {
List<String> result = new ArrayList<>();
if (root == null) return result;
Queue<RankNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
int levelSize = queue.size();
for (int i = 0; i < levelSize; i++) {
RankNode node = queue.poll();
if (i == levelSize - 1) {
result.add(node.name);
}
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
RankNode ceo = new RankNode("CEO");
ceo.left = new RankNode("VP1");
ceo.right = new RankNode("VP2");
ceo.left.left = new RankNode("DIR1");
System.out.println("Right view: " + rightView(ceo));
}
}
Right view: [CEO, VP2, DIR1]
Why is the right view not just the right spine?
If the left subtree is deeper than the right, the last node on a deeper level comes from the left side. Following only right children would miss it. The level-based last-node rule correctly captures any node that happens to be rightmost.
// WRONG: following right children only
public static List<String> naiveRightView(RankNode root) {
List<String> result = new ArrayList<>();
while (root != null) {
result.add(root.name);
root = root.right; // misses left-side nodes!
}
return result;
}
// Returns [CEO, VP2] but misses DIR1
How does the DFS alternative work?
Visit right child before left, carrying depth. The first node seen at each new depth is the rightmost. This uses O(h) space instead of O(w).
public static List<String> rightViewDFS(RankNode root) {
List<String> result = new ArrayList<>();
dfs(root, 0, result);
return result;
}
private static void dfs(RankNode node, int depth, List<String> result) {
if (node == null) return;
if (depth == result.size()) result.add(node.name);
dfs(node.right, depth + 1, result);
dfs(node.left, depth + 1, result);
}
What is the symmetric left view?
The left view captures the first node per level (index == 0) instead of the last. Or in DFS, visit left before right.
// Left view: change capture condition
if (i == 0) result.add(node.name); // first of level
What are the edge cases?
Empty tree, single node, and a tree where every level has only left children.
package com.bank.service;
import com.bank.model.RankNode;
public class RightViewEdgeCases {
public static void main(String[] args) {
System.out.println("Empty: " + RightViewBFS.rightView(null));
System.out.println("Single: " + RightViewBFS.rightView(new RankNode("CEO")));
RankNode leftOnly = new RankNode("CEO");
leftOnly.left = new RankNode("VP");
leftOnly.left.left = new RankNode("DIR");
System.out.println("Left-only: " + RightViewBFS.rightView(leftOnly));
}
}
Empty: []
Single: [CEO]
Left-only: [CEO, VP, DIR]
What is the time and space complexity?
BFS visits each node once, so time is O(n). The queue holds at most one full level, so space is O(w). The DFS version uses O(h) space for the recursion stack.
| Approach | Time | Space |
|---|---|---|
| BFS level-size snapshot | O(n) | O(w) |
| DFS right-first | O(n) | O(h) |
What should a senior engineer know?
The right view, left view, level averages, zigzag traversal, and level-order are all variations of the same BFS level-size snapshot pattern. Recognizing this family saves interview time because the core loop is nearly identical.
In production at National Bank of India, the right view builds a summary of the most senior fallback approver at each escalation rank.
// BFS level variants share this skeleton
while (!queue.isEmpty()) {
int levelSize = queue.size();
for (int i = 0; i < levelSize; i++) {
RankNode node = queue.poll();
// Right view: i == levelSize-1
// Left view: i == 0
// Averages: accumulate sum
if (node.left != null) queue.offer(node.left);
if (node.right != null) queue.offer(node.right);
}
}
Visual Overview
BFS Right View
CEO Level 0: last = CEO
/ \
VP1 VP2 Level 1: last = VP2
/
DIR1 Level 2: last = DIR1
Right view: [CEO, VP2, DIR1]
Note: DIR1 is a left child but rightmost at level 2
DFS Right-First Visit Order Visit: CEO(0) → VP2(1) → VP1(1,skip) → DIR1(2) Result builds: [CEO] → [CEO,VP2] → [CEO,VP2,DIR1]
Key Takeaway
The right view of a binary tree is the last node of each level, which is what you see standing on the right side. You compute it with BFS and the level-size snapshot: enqueue the root, snapshot the queue size at each iteration, drain that many nodes, and capture the one at index levelSize - 1.
The crucial insight is that the right view is not the right spine. If the left subtree runs deeper than the right, the last node on a deeper level comes from the left side. The level-based last-node rule handles this automatically.
The DFS alternative visits the right child first and records the first node seen at each new depth, using O(h) space instead of O(w). 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 produces a summary of the most senior fallback approver at each escalation rank. Some ranks have no right-side branch, so the visible approver is a left-side node, and the level-based rule correctly includes those fallbacks.
Remember one sentence: BFS level-size snapshot, capture the last node per level; that is the right view, not just the right spine.
---