Binary TreesProblem 10 of 35
Right View of Tree
Problem Statement
Given a binary tree, print the right view of the tree. The right view contains all nodes that are the last nodes in their level when viewed from the right side.
Example:
1
/ \
2 3
/ \ \
4 5 6
- Input: Root of the above tree
- Output:
[1, 3, 6]
Approach 1: BFS (Level Order - Last Element)
Intuition
Perform level order traversal and for each level, take only the last element.
Algorithm
- Use BFS to traverse level by level
- For each level, add only the last node to result
- Continue until all levels are processed
java
import java.util.*;
class TreeNode {
int val;
TreeNode left, right;
TreeNode(int x) { val = x; }
}
public class Solution {
public List<Integer> rightViewBFS(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();
// Last node of each level
if (i == levelSize - 1) {
result.add(node.val);
}
if (node.left != null) queue.offer(node.left);
if (node.right != null) queue.offer(node.right);
}
}
return result;
}
}Complexity Analysis
- Time Complexity: O(n) - Each node is visited once
- Space Complexity: O(n) - Queue can hold up to n/2 nodes
Approach 2: Optimal (DFS with Level Tracking)
Intuition
Use DFS and track the maximum level seen so far. Visit right subtree before left subtree. When visiting a node at a new level for the first time, add it to the result.
Algorithm
- Traverse right subtree before left subtree
- Track the current level and max level seen
- If current level > max level, add node to result
- Update max level
java
import java.util.*;
class TreeNode {
int val;
TreeNode left, right;
TreeNode(int x) { val = x; }
}
public class Solution {
private int maxLevel = 0;
public List<Integer> rightView(TreeNode root) {
List<Integer> result = new ArrayList<>();
maxLevel = 0;
rightViewDFS(root, 1, result);
return result;
}
private void rightViewDFS(TreeNode root, int level, List<Integer> result) {
if (root == null) return;
// First node of this level (from right side)
if (level > maxLevel) {
result.add(root.val);
maxLevel = level;
}
// Right before left to get right view
rightViewDFS(root.right, level + 1, result);
rightViewDFS(root.left, level + 1, result);
}
// Alternative: Using result size as level tracker
public List<Integer> rightViewAlt(TreeNode root) {
List<Integer> result = new ArrayList<>();
rightViewDFSAlt(root, 1, result);
return result;
}
private void rightViewDFSAlt(TreeNode root, int level, List<Integer> result) {
if (root == null) return;
if (result.size() < level) {
result.add(root.val);
}
rightViewDFSAlt(root.right, level + 1, result);
rightViewDFSAlt(root.left, level + 1, result);
}
}Complexity Analysis
- Time Complexity: O(n) - Each node is visited exactly once
- Space Complexity: O(h) - Recursion stack depth equals tree height
Key Takeaways
- Right view = last node at each level when traversing left to right
- BFS approach: Take last element of each level
- DFS approach: Visit right child before left, track max level seen
- Right view is often asked in interviews along with left view
- Same pattern can be applied for left view by swapping left/right traversal order
- This is LeetCode #199 - Binary Tree Right Side View