The Binary Tree Right Side View problem asks us to return the list of nodes that are visible when the tree is viewed from the right-hand side.
In other words:
- For every level in the binary tree, we need to find the rightmost node.
- These rightmost nodes, from top to bottom, form the “right side view”.
Here’s the [Problem Link] to begin with.
Examples
Example 1
Input: [1,2,3,null,5,null,4]
Output: [1,3,4]
Explanation:
Level 0 → Rightmost = 1
Level 1 → Rightmost = 3
Level 2 → Rightmost = 4
Example 2
Input: [1,null,3]
Output: [1,3]
Example 3
Input: []
Output: []
Intuition
The main task is to capture the last (rightmost) node at each depth/level.
There are two natural ways to achieve this:
- Breadth-First Search (BFS) – Traverse level by level and pick the last node at each level.
- Depth-First Search (DFS) – Always visit right nodes before left nodes, and record the first node encountered at each depth.
Both methods solve the problem efficiently, but they differ in how they traverse the tree.
Solution 1: BFS (Level Order Traversal)
Approach
- Perform a level-order traversal using a queue.
- At each level, process all nodes from left to right.
- The last node processed at that level is the one visible from the right.
- Append that node’s value to the result list.
This ensures that for every level, the rightmost node is captured.
BFS Code
from collections import deque
class Solution:
def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
if not root:
return []
result = []
queue = deque([root])
while queue:
level_size = len(queue)
for i in range(level_size):
node = queue.popleft()
# If it's the last node at this level, add it to result
if i == level_size - 1:
result.append(node.val)
# Push children into queue
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
return result
BFS Dry Run
Tree: [1,2,3,null,5,null,4]
- Level 0 → [1] → pick 1.
- Level 1 → [2,3] → pick 3.
- Level 2 → [5,4] → pick 4.
Result = [1,3,4]
.
BFS Complexity
- Time Complexity: O(N) – each node is visited once.
- Space Complexity: O(W) – where W is the maximum width of the tree (queue size).
Solution 2: DFS (Right-First Traversal)
Approach
- Perform a DFS traversal, starting from the root.
- Always visit the right child before the left child.
- Keep track of the current depth.
- If it’s the first time visiting this depth, record the node (since the rightmost node will be visited first).
This guarantees that for each depth, the rightmost node is chosen.
DFS Code
class Solution:
def dfs(self, node, depth, result):
if not node:
return
# If this depth is being visited for the first time, add node
if depth == len(result):
result.append(node.val)
# Visit right child first, then left child
self.dfs(node.right, depth + 1, result)
self.dfs(node.left, depth + 1, result)
def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
result = []
self.dfs(root, 0, result)
return result
DFS Dry Run
Tree: [1,2,3,null,5,null,4]
- Start at root (depth 0) → record
1
. - Go right to node
3
(depth 1) → record3
. - Go right again to node
4
(depth 2) → record4
. - Backtrack left → nodes at depths already recorded → ignore.
Result = [1,3,4]
.
DFS Complexity
- Time Complexity: O(N) – each node is visited once.
- Space Complexity: O(H) – where H = height of the tree (recursion stack).
BFS vs DFS Comparison
Aspect | BFS (Level Order) | DFS (Right-First) |
---|---|---|
Traversal | Level by level (queue) | Depth by depth (recursion) |
Order | Pick last node in each level | Pick first node at each depth |
Space Usage | O(W), where W = max width | O(H), where H = tree height |
Implementation | Iterative (queue) | Recursive (stack) |
Both are equally correct. BFS is often more intuitive, while DFS is elegant and shorter.
Conclusion
The Binary Tree Right Side View problem can be solved using:
- BFS: Traverse level by level, pick the last node at each level.
- DFS: Traverse right before left, record the first node at each depth.
Both solutions run in O(N) time and provide the correct right-side view of the tree.
For interview preparation, it’s useful to know both approaches since BFS is straightforward while DFS highlights recursive tree traversal skills.
For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.