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).
1from collections import deque
2
3class TreeNode:
4 def __init__(self, val=0, left=None, right=None):
5 self.val = val
6 self.left = left
7 self.right = right
8
9class Solution:
10 def rightSideView(self, root: TreeNode):
11 if not root:
12 return []
13
14 queue = deque([root])
15 view = []
16
17 while queue:
18 level_length = len(queue)
19 last_node = None
20 for _ in range(level_length):
21 node = queue.popleft()
22 last_node = node.val
23 if node.left:
24 queue.append(node.left)
25 if node.right:
26 queue.append(node.right)
27
28 view.append(last_node)
29
30 return viewThe solution uses a queue to perform BFS. We initialize the queue with the root node, and for each level, we iterate over each node, updating the last node value for that level. At the end of each level iteration, the last node value is added to the result. This gives us the right view of the tree. The space complexity is determined by the maximum width of the tree, and the time complexity is O(n) where n is the number of nodes.
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.
1#include <vector>
2using namespace std;
3
4struct TreeNode {
5 int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:
vector<int> rightSideView(TreeNode* root) {
vector<int> view;
dfs(root, 0, view);
return view;
}
void dfs(TreeNode* node, int level, vector<int>& view) {
if (!node) return;
if (level == view.size()) view.push_back(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.
This solution uses DFS, visiting each node starting from the rightmost node. For each node, if it's the first node visited at that level, it gets added to the result, giving the rightmost view.