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]
Explanation:
Example 2:
Input: root = [1,2,3,4,null,null,null,5]
Output: [1,3,4,5]
Explanation:
Example 3:
Input: root = [1,null,3]
Output: [1,3]
Example 4:
Input: root = []
Output: []
Constraints:
[0, 100].-100 <= Node.val <= 100The goal of #199 Binary Tree Right Side View is to determine which nodes are visible when a binary tree is viewed from the right side. At each depth level, only the rightmost node should appear in the result.
A common strategy is Breadth-First Search (BFS) using a queue for level-order traversal. While processing each level, track the last node visited; this node represents the visible element from the right side. This approach naturally groups nodes by depth, making it easy to capture the rightmost value.
Another effective technique is Depth-First Search (DFS). By traversing the tree in root → right → left order and recording the first node encountered at each depth, you ensure that the rightmost node is captured before others.
Both methods traverse every node in the tree once, giving efficient performance. The choice between BFS and DFS usually depends on coding preference and recursion comfort.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Breadth-First Search (Level Order) | O(n) | O(n) |
| Depth-First Search (Right-first traversal) | O(n) | O(h) average, O(n) worst case |
NeetCode
The Breadth-First Search (BFS) approach involves traversing the tree level by level using a queue. For each level, we capture the last node's value visible when viewed from the right side. This can be done by iterating through each level and storing the value of the last node encountered. This approach ensures that the elements are captured in top-to-bottom order as required.
Time Complexity: O(n), where n is the number of nodes in the tree.
Space Complexity: O(w), where w is the maximum width of the tree (at the level with the most nodes).
1import java.util.ArrayList;
2import java.util.LinkedList;
3import java.util.List;
4import java.util.Queue;
5
6class TreeNode {
7 int val;
8 TreeNode left;
9 TreeNode right;
10 TreeNode() {}
11 TreeNode(int val) { this.val = val; }
12 TreeNode(int val, TreeNode left, TreeNode right) {
13 this.val = val;
14 this.left = left;
15 this.right = right;
16 }
17}
18
19public class Solution {
20 public List<Integer> rightSideView(TreeNode root) {
21 List<Integer> view = new ArrayList<>();
22 if (root == null) return view;
23
24 Queue<TreeNode> queue = new LinkedList<>();
25 queue.add(root);
26
27 while (!queue.isEmpty()) {
28 int levelSize = queue.size();
29 Integer lastNode = null;
30 for (int i = 0; i < levelSize; i++) {
31 TreeNode node = queue.poll();
32 lastNode = node.val;
33 if (node.left != null) {
34 queue.add(node.left);
35 }
36 if (node.right != null) {
37 queue.add(node.right);
38 }
39 }
40 view.add(lastNode);
41 }
42
43 return view;
44 }
45}We use a queue to traverse each level of the tree. For each level, we store the last node encountered, as this will be the rightmost node visible from that level. This approach guarantees capturing the right side view, storing the rightmost visible node at each tree level.
In this approach, a recursive Depth-First Search (DFS) is utilized. It traverses the tree from the root and prioritizes the right child before the left child at each node. By keeping track of the current level, we ensure to capture only the first node visited at that level, which represents the right view at that height.
Time Complexity: O(n), where n is the number of nodes in the tree.
Space Complexity: O(h), where h is the height of the tree, considering the space used for recursion stack.
1using System.Collections.Generic;
2
3public class TreeNode {
4 public int val;
5 public TreeNode left;
public TreeNode right;
public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
this.val = val;
this.left = left;
this.right = right;
}
}
public class Solution {
public IList<int> RightSideView(TreeNode root) {
var view = new List<int>();
DFS(root, 0, view);
return view;
}
private void DFS(TreeNode node, int level, List<int> view) {
if (node == null) return;
if (level == view.Count) {
view.Add(node.val);
}
DFS(node.right, level + 1, view);
DFS(node.left, level + 1, view);
}
}Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, variations of this problem are frequently asked in FAANG and other top tech interviews. It tests understanding of tree traversal techniques, especially BFS level processing and DFS depth tracking.
The optimal approach is typically a breadth-first search (level order traversal). By processing nodes level by level and selecting the last node at each level, you capture the node visible from the right side. A right-first depth-first search can also achieve the same result efficiently.
Yes, DFS works well if you traverse the tree in root-right-left order. By recording the first node visited at each depth level, you ensure that the rightmost node for that level is captured.
A queue is commonly used for the BFS solution because it naturally supports level-order traversal of the tree. For a DFS approach, recursion or an explicit stack works well while tracking the depth of each node.
The DFS strategy involves recursion, starting with the right child node at each step. This ensures capturing the rightmost nodes of the tree from top to bottom. Nodes are added to the list if they are the first nodes encountered at their respective levels.