145. Binary Tree Right Side View
🔗 LeetCode Problem: 199. Binary Tree Right Side View
📊 Difficulty: Medium
🏷️ Topics: Binary Trees, BFS, DFS, Level Order, Recursion
Problem Statement
Given the root of a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.
Example 1:
Input: root = [1,2,3,null,5,null,4]
Output: [1,3,4]
Example 2:
Input: root = [1,null,3]
Output: [1,3]
Example 3:
Input: root = []
Output: []
Constraints:
- The number of nodes in the tree is in the range [0, 100]
- -100 <= Node.val <= 100
🌳 Visual Understanding - The Right Side View!
What Does "Right Side View" Mean?
Imagine looking at the tree from the RIGHT side:
Tree (top view):
1
/ \
2 3
\ \
5 4
Right side view (what you see from right):
1 ← Level 0: See 1
3 ← Level 1: See 3 (rightmost at this level)
4 ← Level 2: See 4 (rightmost at this level)
Result: [1, 3, 4]
You see the RIGHTMOST node at each level! 🎯
Visual Breakdown:
Tree:
1 Level 0: nodes [1] → rightmost = 1
/ \
2 3 Level 1: nodes [2, 3] → rightmost = 3
\ \
5 4 Level 2: nodes [5, 4] → rightmost = 4
Right side view = Last node at each level = [1, 3, 4]
Another Example:
Tree:
1 Level 0: [1] → 1
/ \
2 3 Level 1: [2, 3] → 3
/
4 Level 2: [4] → 4
Right side view: [1, 3, 4]
Even though 4 is on the LEFT side of tree,
it's the RIGHTMOST (only) node at level 2! 🎯
Edge Case - Right-Skewed Tree:
Tree:
1
\
2
\
3
Right side view: [1, 2, 3]
All nodes visible from right! ✓
Edge Case - Left-Skewed Tree:
Tree:
1
/
2
/
3
Right side view: [1, 2, 3]
Even though all on left,
they're the ONLY nodes at each level! ✓
🧠 The AHA Moment - Two Perspectives!
Perspective 1: Level Order (BFS)
"Right side view" = "Last node at each level"
We already know level order traversal!
→ Just take the LAST node from each level!
Problem 140 (Level Order): [[1], [2, 3], [5, 4]]
Problem 145 (Right View): [1, 3, 4]
↑ ↑ ↑
Last of each level!
This is Problem 140 + take last! 🎯
Perspective 2: DFS with Level Tracking
Visit nodes: Root → Right → Left (prioritize right!)
Key insight:
First node we see at each level = rightmost!
Why?
We visit right children before left
So right nodes are encountered first
Track which levels we've seen
Only add if it's the FIRST time seeing that level!
DFS with "right-first" traversal! 🔑
🎯 Solution 1: BFS - Level Order (Most Intuitive!)
The Strategy:
1. Do standard level order traversal (BFS)
2. For each level, take the LAST node
3. Add to result
Simple modification of Problem 140! ✓
Implementation:
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 levelSize = queue.size();
TreeNode rightmost = null; // Track rightmost
// Process all nodes at current level
for (int i = 0; i < levelSize; i++) {
TreeNode node = queue.poll();
rightmost = node; // Last one will be rightmost!
// Add children for next level
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
// Add the rightmost node of this level
// WHY? It's visible from right side!
result.add(rightmost.val);
}
return result;
}
}
Alternative - Take Last Directly:
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 levelSize = queue.size();
for (int i = 0; i < levelSize; i++) {
TreeNode node = queue.poll();
// If this is the last node of level
if (i == levelSize - 1) {
result.add(node.val); // Add to result!
}
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
}
return result;
}
}
Why This Works:
Level order processes left to right:
Level 1: process 2, then 3
Last processed = 3 = rightmost! ✓
Queue ensures level-by-level:
Level 0: [1] → add 1
Level 1: [2, 3] → add 3
Level 2: [5, 4] → add 4
Result: [1, 3, 4] ✓
🎯 Solution 2: DFS - Right-First Traversal (Elegant!)
The Strategy:
Visit nodes: Root → Right → Left
Key observation:
First node visited at each level = rightmost!
Why?
We go right BEFORE left
So rightmost nodes encountered first!
Track levels seen:
If level not seen before → add to result
If level seen → skip (we already have rightmost)
Implementation:
class Solution {
public List<Integer> rightSideView(TreeNode root) {
List<Integer> result = new ArrayList<>();
dfs(root, 0, result);
return result;
}
private void dfs(TreeNode node, int level, List<Integer> result) {
// Base case
if (node == null) {
return;
}
// If this is the first time we see this level
// WHY? First node at each level (going right first) is rightmost!
if (level == result.size()) {
result.add(node.val);
}
// Visit RIGHT first! (key to this approach)
// WHY? Right nodes should be seen before left nodes
dfs(node.right, level + 1, result);
// Then visit left
dfs(node.left, level + 1, result);
}
}
Why Right-First Matters:
Tree:
1
/ \
2 3
\ \
5 4
DFS visits (right-first):
1 (level 0) → first time seeing level 0 → add 1
3 (level 1) → first time seeing level 1 → add 3
4 (level 2) → first time seeing level 2 → add 4
2 (level 1) → already seen level 1 → skip
5 (level 2) → already seen level 2 → skip
Result: [1, 3, 4] ✓
If we did LEFT-first:
1 (level 0) → add 1
2 (level 1) → add 2 (WRONG!)
5 (level 2) → add 5 (WRONG!)
Would get LEFT side view! ✗
🔍 Detailed Dry Run - BFS Approach
Tree:
1
/ \
2 3
\ \
5 4
Complete BFS Execution:
INITIAL:
queue = [1]
result = []
═══════════════════════════════════════
LEVEL 0:
═══════════════════════════════════════
levelSize = 1
rightmost = null
Iteration 0 (i = 0):
node = poll() = 1
rightmost = 1 (last node in loop)
Add children:
left(2) → queue = [2]
right(3) → queue = [2, 3]
result.add(1) → [1]
State:
queue = [2, 3]
result = [1]
═══════════════════════════════════════
LEVEL 1:
═══════════════════════════════════════
levelSize = 2
rightmost = null
Iteration 0 (i = 0):
node = poll() = 2
rightmost = 2
Add children:
left(null) skip
right(5) → queue = [3, 5]
Iteration 1 (i = 1):
node = poll() = 3
rightmost = 3 (last! overwrites 2)
Add children:
left(null) skip
right(4) → queue = [5, 4]
result.add(3) → [1, 3]
State:
queue = [5, 4]
result = [1, 3]
═══════════════════════════════════════
LEVEL 2:
═══════════════════════════════════════
levelSize = 2
rightmost = null
Iteration 0 (i = 0):
node = poll() = 5
rightmost = 5
No children
Iteration 1 (i = 1):
node = poll() = 4
rightmost = 4 (last!)
No children
result.add(4) → [1, 3, 4]
State:
queue = []
result = [1, 3, 4]
═══════════════════════════════════════
DONE! Queue empty
═══════════════════════════════════════
FINAL: [1, 3, 4] ✓
🔍 Detailed Dry Run - DFS Approach
Tree:
1
/ \
2 3
\ \
5 4
Complete DFS Execution (Right-First):
CALL STACK VISUALIZATION:
Level 0: dfs(1, 0, [])
│
├─ node = 1, level = 0
├─ result.size() = 0, level = 0 → MATCH!
├─ Add 1: result = [1]
│
├─ RIGHT: dfs(3, 1, [1]) ────────────────────┐
│ │
│ Level 1: dfs(3, 1, [1]) │
│ │ │
│ ├─ node = 3, level = 1 │
│ ├─ result.size() = 1, level = 1 → MATCH! │
│ ├─ Add 3: result = [1, 3] │
│ │ │
│ ├─ RIGHT: dfs(4, 2, [1, 3]) ─────────┐ │
│ │ │ │
│ │ Level 2: dfs(4, 2, [1, 3]) │ │
│ │ │ │ │
│ │ ├─ node = 4, level = 2 │ │
│ │ ├─ result.size() = 2, level = 2 │ │
│ │ ├─ MATCH! Add 4: result = [1,3,4] │ │
│ │ ├─ RIGHT: dfs(null) → return │ │
│ │ ├─ LEFT: dfs(null) → return │ │
│ │ └─ return │ │
│ │ │ │
│ ├─ LEFT: dfs(null, 2) → return │ │
│ └─ return │ │
│ │
├─ LEFT: dfs(2, 1, [1, 3, 4]) ───────────────┐
│ │
│ Level 1: dfs(2, 1, [1, 3, 4]) │
│ │ │
│ ├─ node = 2, level = 1 │
│ ├─ result.size() = 3, level = 1 │
│ ├─ 3 != 1 → NO MATCH, skip! │
│ │ (already have level 1: node 3) │
│ │ │
│ ├─ RIGHT: dfs(5, 2, [1, 3, 4]) ──────┐ │
│ │ │ │
│ │ Level 2: dfs(5, 2, [1, 3, 4]) │ │
│ │ │ │ │
│ │ ├─ node = 5, level = 2 │ │
│ │ ├─ result.size() = 3, level = 2 │ │
│ │ ├─ 3 != 2 → NO MATCH, skip! │ │
│ │ │ (already have level 2: node 4)│ │
│ │ ├─ RIGHT: dfs(null) → return │ │
│ │ ├─ LEFT: dfs(null) → return │ │
│ │ └─ return │ │
│ │ │ │
│ ├─ LEFT: dfs(null, 2) → return │ │
│ └─ return │ │
│ │
└─ FINAL: [1, 3, 4] │
Result: [1, 3, 4] ✓
Visit Order Visualization:
Tree with visit order:
1 (1st, level 0) → add to result: [1]
/ \
2 3 (2nd, level 1) → add to result: [1, 3]
\ \
5 4 (3rd, level 2) → add to result: [1, 3, 4]
Then visit left side:
2 (4th, level 1) → skip (already have level 1)
\
5 (5th, level 2) → skip (already have level 2)
Right-first ensures rightmost nodes seen first! 🎯
📊 Comparison - BFS vs DFS
BFS Approach:
// Level order, take last of each level
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
int levelSize = queue.size();
TreeNode rightmost = null;
for (int i = 0; i < levelSize; i++) {
TreeNode node = queue.poll();
rightmost = node; // Last is rightmost
if (node.left != null) queue.offer(node.left);
if (node.right != null) queue.offer(node.right);
}
result.add(rightmost.val);
}
Pros:
✓ More intuitive (clear level-by-level)
✓ Easy to understand
✓ Direct translation: "last of each level"
Cons:
✗ Uses queue (O(w) space)
✗ More code
DFS Approach:
// Right-first traversal, track levels
private void dfs(TreeNode node, int level, List<Integer> result) {
if (node == null) return;
if (level == result.size()) {
result.add(node.val); // First at level = rightmost
}
dfs(node.right, level + 1, result); // Right first!
dfs(node.left, level + 1, result);
}
Pros:
✓ Cleaner code (fewer lines)
✓ Elegant solution
✓ Uses recursion (natural for trees)
Cons:
✗ Less intuitive initially
✗ Must remember right-first order
Which to Use?
For interviews: BFS (easier to explain)
→ "Take last node of each level"
→ Clear, intuitive
→ Builds on level order knowledge
For elegance: DFS (shorter code)
→ "Right-first, first of each level"
→ Shows deeper understanding
→ Can mention as optimization
Both are O(n) time, O(n) space!
Choose based on clarity! ✨
📊 Complexity Analysis
Both Solutions:
Time Complexity: O(n)
BFS: Visit each node once in queue
DFS: Visit each node once in recursion
Both: O(n)
Space Complexity: O(n)
BFS:
Queue: O(w) where w = max width
Worst case (complete tree): O(n/2) = O(n)
Result: O(h) where h = height
Total: O(n)
DFS:
Recursion stack: O(h) where h = height
Worst case (skewed): O(n)
Result: O(h)
Total: O(n)
Both: O(n) worst case
⚠️ Common Mistakes
Mistake 1: Wrong DFS Order (Left-First)
// ❌ WRONG - Gives LEFT side view!
private void dfs(TreeNode node, int level, List<Integer> result) {
if (node == null) return;
if (level == result.size()) {
result.add(node.val);
}
dfs(node.left, level + 1, result); // LEFT first!
dfs(node.right, level + 1, result); // RIGHT second
}
// Tree: 1
// / \
// 2 3
// Result: [1, 2] ✗ (LEFT side view!)
// ✓ CORRECT - Right first!
dfs(node.right, level + 1, result); // RIGHT first!
dfs(node.left, level + 1, result); // LEFT second
// Result: [1, 3] ✓
Mistake 2: Adding All Nodes at Level
// ❌ WRONG - Adds all nodes at each level
while (!queue.isEmpty()) {
int levelSize = queue.size();
for (int i = 0; i < levelSize; i++) {
TreeNode node = queue.poll();
result.add(node.val); // Adds ALL! ✗
if (node.left != null) queue.offer(node.left);
if (node.right != null) queue.offer(node.right);
}
}
// Result: [1, 2, 3, 5, 4] ✗ (all nodes!)
// ✓ CORRECT - Only add last
TreeNode rightmost = null;
for (int i = 0; i < levelSize; i++) {
TreeNode node = queue.poll();
rightmost = node; // Track last
// ...
}
result.add(rightmost.val); // Add only last ✓
Mistake 3: Wrong Level Check in DFS
// ❌ WRONG - Always adds
private void dfs(TreeNode node, int level, List<Integer> result) {
if (node == null) return;
if (level >= result.size()) { // >= allows duplicates! ✗
result.add(node.val);
}
dfs(node.right, level + 1, result);
dfs(node.left, level + 1, result);
}
// Can add multiple nodes per level! ✗
// ✓ CORRECT - Exact match
if (level == result.size()) { // Only if exact match! ✓
result.add(node.val);
}
Mistake 4: Not Handling Empty Tree
// ❌ WRONG - NullPointerException!
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root); // If root is null, adds null!
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
result.add(node.val); // NPE if node is null! ✗
}
// ✓ CORRECT - Check first
if (root == null) {
return result; // Return empty list
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root); // Now safe ✓
🎯 Pattern Recognition - Level-Based Problems
Core Pattern: Level Order Variations
Template for level-based problems:
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
int levelSize = queue.size();
// Process level
for (int i = 0; i < levelSize; i++) {
TreeNode node = queue.poll();
// MODIFY HERE based on problem!
processNode(node, i, levelSize);
if (node.left != null) queue.offer(node.left);
if (node.right != null) queue.offer(node.right);
}
}
Related Problems:
1. Binary Tree Level Order (Problem 140)
Base problem
Collect all nodes at each level
Result: [[1], [2, 3], [5, 4]]
2. Zigzag Level Order (Problem 141)
Alternate direction per level
Reverse odd levels
Result: [[1], [3, 2], [5, 4]]
3. Right Side View (Problem 145)
Take LAST node of each level
Result: [1, 3, 4]
4. Left Side View
Take FIRST node of each level
Similar to right side, just index 0
Result: [1, 2, 5]
5. Average of Levels
Calculate average per level
sum / count for each level
6. Binary Tree Level Order Bottom-Up
Level order then reverse
Collections.reverse(result)
When to Use This Pattern:
✓ Problem mentions "level"
✓ Need horizontal processing
✓ View from a side (left/right)
✓ Level-based calculation
✓ Layer-by-layer traversal
📝 Quick Revision Notes
🎯 Core Concept
Right side view = Last node at each level. Two approaches: (1) BFS - level order, take last of each level (intuitive), (2) DFS - right-first traversal, first node at each level is rightmost (elegant). BFS uses queue, DFS uses recursion with level tracking. Both O(n) time and space.
⚡ Quick Implementation
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode() {}
TreeNode(int val) { this.val = val; }
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
public static TreeNode buildTree(Integer[] arr) {
if (arr == null || arr.length == 0 || arr[0] == null) {
return null;
}
TreeNode root = new TreeNode(arr[0]);
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
int i = 1;
while (!queue.isEmpty() && i < arr.length) {
TreeNode current = queue.poll();
// Process left child
if (i < arr.length) {
if (arr[i] != null) {
current.left = new TreeNode(arr[i]);
queue.offer(current.left);
}
i++;
}
// Process right child
if (i < arr.length) {
if (arr[i] != null) {
current.right = new TreeNode(arr[i]);
queue.offer(current.right);
}
i++;
}
}
return root;
}
public static void print(TreeNode root) {
if (root == null) {
System.out.println("[]");
return;
}
List<String> result = new ArrayList<>();
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
if (node != null) {
result.add(String.valueOf(node.val));
queue.offer(node.left);
queue.offer(node.right);
} else {
result.add("null");
}
}
while (!result.isEmpty() && result.get(result.size() - 1).equals("null")) {
result.remove(result.size() - 1);
}
System.out.println(result);
}
}
class Solution {
public List<Integer> rightSideView(TreeNode root) {
List<Integer> res = new ArrayList<>();
if(root == null) {
return res;
}
// // Approach 1 - iterative BFS (level order traversal - take last element at each level)
// iterativeBFS(root, res);
// Approach 2 - recursive DFS (smart. But above is enough. Just to know)
recursiveDFS(root, 0, res);
return res;
}
private void recursiveDFS(TreeNode root, int level, List<Integer> res) {
// normal base case.
if(root == null) {
return;
}
// When you always process right node first, take that value and add to the result.
// So, at each level, list size gets increased 1 by 1.
// When right subtree gets called, level also gets increased and we match the size.
// For any other call, below if condition fails for that particular level.
// For example, at level 1, res also size is 1. Any elements gets try to add, level and size will not match and hence no add to list.
if(level == res.size()) {
res.add(root.val);
}
if(root.right != null) {
recursiveDFS(root.right, 1 + level, res);
}
if(root.left != null) {
recursiveDFS(root.left, 1 + level, res);
}
}
private void iterativeBFS(TreeNode root, List<Integer> res) {
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
int size = queue.size();
for(int i = 0; i < size; i++) {
TreeNode curr = queue.poll();
// add only last element. This is the CHANGE from normal BFS.
if(i == size - 1) {
res.add(curr.val);
}
// Below 2 blocks are same.
if(curr.left != null) {
queue.offer(curr.left);
}
if(curr.right != null) {
queue.offer(curr.right);
}
}
}
}
public static void main(String[] args) {
Solution s = new Solution();
System.out.println(s.rightSideView(TreeNode.buildTree(new Integer[] {1,2,3,null,5,null,4}))); // 1,3,4
System.out.println(s.rightSideView(TreeNode.buildTree(new Integer[] {1,2,3,4,null,null,null,5}))); // 1,3,4,5
System.out.println(s.rightSideView(TreeNode.buildTree(new Integer[] {1,null,3}))); // 1,3
System.out.println(s.rightSideView(TreeNode.buildTree(new Integer[] {}))); // empty
}
}
🔑 Key Insights
Problem Composition:
Problem 140: Level Order
[[1], [2, 3], [5, 4]]
Problem 145: Right Side View
[1, 3, 4]
Take last from each level!
This is COMPOSITION:
Level Order + Take Last = Right View
Reuse patterns! 🔧
DFS Right-First Magic:
Why right-first order matters:
Tree: 1
/ \
2 3
Right-first: 1 → 3 → 2
Visit 3 before 2 at level 1
So 3 added to result (first at level 1)
When we reach 2, level 1 already in result, skip!
Left-first: 1 → 2 → 3
Visit 2 before 3 at level 1
So 2 added (WRONG - left view!)
Order is CRITICAL! ⚡
Level Size Check:
if (level == result.size())
Why this works:
result.size() = number of levels processed
level = current depth (0-indexed)
If equal: First node at NEW level!
If not equal: Already processed this level
Elegant way to track visited levels! 🎯
🎪 Memory Aid
"Right view = Last of each level!"
"DFS: Right before Left!"
"Level == size → First visit!"
"Build on level order!" ✨
⚠️ Don't Forget
- BFS: take LAST of each level (rightmost!)
- DFS: visit RIGHT before left (right-first!)
- Level check: level == result.size() (exact match!)
- Handle null root (return empty list!)
- Both approaches O(n) (same complexity!)
- Build on Problem 140 (level order base!)
🎉 Congratulations!
You've mastered level-based view problems!
What You Learned:
✅ Right side view concept - Rightmost at each level
✅ BFS approach - Level order + take last
✅ DFS approach - Right-first traversal
✅ Level tracking - Using result.size()
✅ Problem composition - Building on level order
✅ Pattern variations - Left view, averages, etc.
The Pattern Library Growing:
You now have:
✓ Level order (Problem 140)
✓ Zigzag (Problem 141)
✓ Right side view (Problem 145)
Next variations:
- Left side view (first of each level)
- Bottom-up (reverse result)
- Average of levels (sum/count)
All use the SAME template! 🧰
Interview Mastery:
Interviewer: "Right side view of tree"
Your thought process:
1. "Last node of each level" ✓
2. "Use level order BFS" ✓
3. "Track rightmost in loop" ✓
4. Code in 5 minutes ✓
Can also mention:
"DFS approach exists - right-first traversal"
Shows depth of knowledge! 💡
You're crushing level-based problems! 🌳✨🎯