Binary Tree Right Side View - Solution & Explanation
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]
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:
- The number of nodes in the tree is in the range
[0, 100]. -100 <= Node.val <= 100
Approach Overview
Problem Overview: Given the root of a binary tree, return the list of node values visible when the tree is viewed from the right side. At each depth level, only the rightmost node should appear in the result.
Approach 1: Breadth-First Search (BFS) using Queue (O(n) time, O(n) space)
This approach performs a level-order traversal using a queue. Process the tree level by level and track how many nodes exist at the current depth. As you iterate through nodes in the same level, the last node processed represents the rightmost node visible from that level. Add this node's value to the result list. Each node is enqueued once and dequeued once, which gives O(n) time complexity, while the queue can hold up to one full level of nodes, leading to O(n) space in the worst case.
BFS works well because the problem is naturally defined by levels of a tree. You simply detect the final node encountered in each level iteration. This method is straightforward and easy to implement during interviews, especially when you are already using a queue for level traversal of a binary tree. The algorithm scales cleanly for skewed and balanced trees alike.
Approach 2: Depth-First Search (DFS) Right-First Traversal (O(n) time, O(h) space)
The DFS approach explores the tree recursively while prioritizing the right subtree before the left subtree. Maintain the current depth during recursion and track the maximum depth already recorded in the result list. Whenever you visit a node at a depth equal to the current result size, it means this is the first node encountered at that level from the right side, so you append its value.
This works because visiting the right child first guarantees the first node seen at each depth is the visible one. The recursion stack stores at most the height of the tree, resulting in O(h) space where h is the tree height. In the worst case of a skewed tree, that becomes O(n). DFS is common when working with recursive traversal patterns in depth-first search problems.
Compared to BFS, this method avoids explicitly storing full levels in a queue and instead relies on recursion depth tracking. It integrates naturally with many tree-recursion templates used in tree problems.
Recommended for interviews: Both BFS and DFS run in O(n) time and are accepted solutions. Interviewers often expect the BFS level-order solution first because it directly models "one node per level" visibility. Demonstrating the DFS right-first approach afterward shows deeper understanding of traversal order and recursion patterns.
Approach 1: Breadth-First Search (BFS) using Queue
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.
The 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.
Complexity
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).
Approach 2: Depth-First Search (DFS)
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.
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.
Complexity
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.
Approach 3: BFS
We can use breadth-first search (BFS) and define a queue q to store the nodes. We start by putting the root node into the queue. Each time, we take out all the nodes of the current level from the queue. For the current node, we first check if the right subtree exists; if it does, we put the right subtree into the queue. Then, we check if the left subtree exists; if it does, we put the left subtree into the queue. This way, the first node taken out from the queue each time is the rightmost node of that level.
The time complexity is O(n), and the space complexity is O(n). Here, n is the number of nodes in the binary tree.
Code
Python
Java
C++
Go
TypeScript
Rust
JavaScript
Approach 4: DFS
Use DFS (depth-first search) to traverse the binary tree. Each time, traverse the right subtree first, then the left subtree. This way, the first node visited at each level is the rightmost node of that level.
The time complexity is O(n), and the space complexity is O(n). Here, n is the number of nodes in the binary tree.
Code
Python
Java
C++
Go
TypeScript
JavaScript
Rust
Complexity Comparison
| Approach | Complexity |
|---|---|
| Breadth-First Search (BFS) using Queue | Time Complexity: O(n), where n is the number of nodes in the tree. |
| Depth-First Search (DFS) | Time Complexity: O(n), where n is the number of nodes in the tree. |
| BFS | — |
| DFS | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Breadth-First Search (Queue Level Order) | O(n) | O(n) | Best when reasoning level-by-level in a binary tree and identifying the last node in each level |
| Depth-First Search (Right-First Traversal) | O(n) | O(h) | Useful when using recursive tree traversal templates and tracking depth |
Video Solution
Binary Tree Right Side View - Breadth First Search - Leetcode 199 • NeetCode • 153,422 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Binary Tree Right Side View easy or hard?
How to solve Binary Tree Right Side View in O(n)?
Binary Tree Right Side View Python or Java solution
What is the best approach for Binary Tree Right Side View?
What data structure is used in Binary Tree Right Side View?
What is the time complexity of Binary Tree Right Side View?
Is Binary Tree Right Side View asked at Google, Amazon, or Meta?
Ready to solve this problem?
Practice Binary Tree Right Side View with our built-in code editor and test cases.
Practice on FleetCode