Binary Tree Right Side View
Last Updated: March 29, 2026
Understanding the Problem
We are looking at a binary tree from the right side. For each level of the tree, we want the rightmost visible node. That does not always mean "the right child." If a level has nodes only in the left subtree, the leftmost node at that level is still the one you would see from the right, because nothing blocks it.
So the real question is: for every depth level in the tree, what is the last node when we scan left to right? This reframes the problem from a spatial "standing on the right" visualization to a concrete algorithmic task: find the last node at each level.
This connects directly to level-order traversal. If we process each level left to right, the last node we process at each level is our answer. But we can also solve this with DFS by visiting the right subtree first.
Key Constraints:
Number of nodes in range [0, 100]— Extremely small input. Even an O(n^2) approach would finish instantly. The focus here is on choosing the right traversal strategy, not on optimizing for performance.-100 <= Node.val <= 100— Node values can be negative. This does not affect our traversal logic.- The tree can be empty (0 nodes), so we need to handle the null root case.
Approach 1: BFS (Level Order Traversal)
Intuition
The most natural way to think about this problem is level by level. If we process all nodes at each level from left to right, the last node we see at each level is the one visible from the right side. This is exactly what BFS does.
We use a queue to process nodes level by level. At each level, we dequeue all the current nodes, and whatever node we dequeue last is the right side view for that level. We just need to keep track of the last value processed in each level's iteration.
Algorithm
- If the root is null, return an empty list.
- Create a queue and add the root.
- While the queue is not empty:
- Record the current queue size as
levelSize. - Process exactly
levelSizenodes from the queue. - For each node, enqueue its left and right children (if they exist).
- The last node processed in this level is the right side view node. Add its value to the result.
- Return the result list.
Example Walkthrough
Code
- Time Complexity: O(n). We visit every node exactly once. Each node is enqueued and dequeued once, and both operations are O(1).
- Space Complexity: O(n). The queue holds at most one level's worth of nodes. In the worst case (a complete binary tree), the bottom level has roughly n/2 nodes.
BFS is already O(n) in time, which is optimal. But the queue holds an entire level at once, which can be up to n/2 nodes for a wide tree. What if we used DFS instead, where the only extra space is the recursion stack (proportional to tree height, not width)?
Approach 2: DFS (Right-First Traversal)
Intuition
Instead of processing level by level and picking the last node, what if we always visited the right subtree first? If we do a depth-first traversal where we go right before left, then the first node we encounter at each new depth level is guaranteed to be the rightmost node at that level.
The trick is knowing when we have reached a "new" depth. We can track this by comparing the current depth against the size of our result list. If depth == result.size(), we have not recorded any node at this depth yet, so the current node is the first (rightmost) one we have seen at this level.
This is elegant because it flips the perspective. Instead of scanning each level and keeping the last node, we visit in an order that naturally hits the rightmost node first.
The core principle is that in a right-first DFS, the traversal order guarantees the rightmost node at each level is visited before any other node at the same level. Since we only record the first node we encounter at each new depth, and right-first ordering ensures that first node is the rightmost, we get exactly the right side view.
This works even when the left subtree is deeper than the right subtree. If the right subtree has depth 3 but the left subtree extends to depth 5, levels 4 and 5 only have nodes in the left subtree. When the DFS backtracks to explore the left side, it will find new depths (4 and 5) and record those left-subtree nodes. This is correct because they are the only nodes at those depths, so they are visible from the right.
Algorithm
- If the root is null, return an empty list.
- Create an empty result list.
- Define a recursive function
dfs(node, depth): - If
nodeis null, return. - If
depthequals the size ofresult, this is the first node we have seen at this depth. Addnode.valto the result. - Recurse on the right child with
depth + 1(right first!). - Recurse on the left child with
depth + 1. - Call
dfs(root, 0)and return the result.
Example Walkthrough
Code
- Time Complexity: O(n). We visit every node exactly once. Each visit does O(1) work (a comparison and possibly an append).
- Space Complexity: O(h), where h is the height of the tree. The recursion stack goes as deep as the tree height. For a balanced tree, h = O(log n). For a completely skewed tree, h = O(n).