LeetCode 199 - Binary Tree Right Side View
The problem gives us the root node of a binary tree and asks us to determine which nodes are visible when looking at the tree from the right side.
Difficulty: 🟡 Medium
Topics: Tree, Depth-First Search, Breadth-First Search, Binary Tree
Solution
Problem Understanding
The problem gives us the root node of a binary tree and asks us to determine which nodes are visible when looking at the tree from the right side.
A binary tree is a hierarchical data structure where each node can have at most two children, called the left child and the right child. The input is provided as the root of that structure. The output should be a list of node values representing the nodes that would be visible if someone stood to the right of the tree and looked toward it.
At every depth level of the tree, only one node can be visible from the right side. Specifically, the visible node is the rightmost node at that depth.
For example, consider this tree:
1
/ \
2 3
\ \
5 4
At depth 0, we see node 1.
At depth 1, nodes 2 and 3 exist, but 3 blocks 2 from the right-side perspective.
At depth 2, nodes 5 and 4 exist, but 4 is farther to the right.
So the result is:
[1, 3, 4]
The constraints tell us that the tree contains at most 100 nodes. This is relatively small, so even less optimized approaches could technically pass. However, the goal is to design a clean and efficient solution that scales properly and demonstrates correct tree traversal techniques.
Several edge cases are important:
- The tree may be empty, meaning
rootisNone. In that case, the answer should be an empty list. - The tree may contain only left children. Even though there are no right children, every node is still visible because nothing blocks it from the right side.
- The tree may contain only right children. In this case, every node is also visible.
- The tree may be unbalanced, meaning one subtree is much deeper than the other.
- Nodes can contain negative values, but this does not affect the traversal logic.
Approaches
A brute-force approach would first group nodes by depth level and then determine which node is the farthest to the right at each level. One way to do this is to perform a full traversal of the tree while storing every node encountered at every depth. After the traversal finishes, we could select the last node stored for each level.
This works because the last node visited at a level during a left-to-right traversal is the rightmost node. However, this approach stores more information than necessary because we only care about one node per level, not all nodes.
A better solution comes from recognizing that we can determine the visible node while traversing the tree. If we process nodes level by level using Breadth-First Search, the last node processed at each level is automatically the visible right-side node.
Another elegant optimization uses Depth-First Search with right-first traversal. By visiting the right subtree before the left subtree, the first node encountered at each depth is the visible node.
Both approaches are optimal with linear complexity. In this guide, we will focus on the Breadth-First Search solution because it directly models the concept of levels in the tree and is very intuitive for this problem.
| Approach | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Brute Force | O(n) | O(n) | Stores all nodes at every level before selecting the rightmost |
| Optimal | O(n) | O(n) | Uses BFS level traversal and records only the last node per level |
Algorithm Walkthrough
We will use Breadth-First Search with a queue.
Step-by-step process
- First, check whether the tree is empty.
If root is None, there are no visible nodes, so we immediately return an empty list.
2. Create a queue and initialize it with the root node.
A queue is ideal for Breadth-First Search because it processes nodes level by level in the same order they appear in the tree. 3. Create an empty result list.
This list will store the visible node at each depth. 4. Start a loop that continues while the queue is not empty.
Each iteration of this loop processes exactly one depth level of the tree. 5. Determine the number of nodes currently in the queue.
This value represents the number of nodes at the current depth level. 6. Process every node in the current level.
Remove nodes one by one from the queue.
For each node:
- Add its left child to the queue if it exists.
- Add its right child to the queue if it exists.
- Identify the rightmost node.
During the loop for the current level, the last node processed is the rightmost node because BFS processes nodes from left to right.
When processing the final node of the level, append its value to the result list. 8. Continue until all levels are processed.
Once the queue becomes empty, every node has been visited and every visible node has been recorded. 9. Return the result list.
Why it works
Breadth-First Search processes the tree one depth level at a time. Within each level, nodes are processed from left to right because children are added to the queue in left-first order. Therefore, the final node processed at each level is always the rightmost node. Since the rightmost node is exactly what would be visible from the right side, recording that node at every level guarantees the correct answer.
Python Solution
from collections import deque
from typing import List, Optional
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
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 node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
if i == level_size - 1:
result.append(node.val)
return result
The implementation begins by handling the empty tree case. If the root is None, the function immediately returns an empty list.
The deque from Python's collections module is used because queue operations such as popleft() are efficient in constant time.
The main loop processes one tree level at a time. Before iterating through a level, we record the current queue size in level_size. This ensures that only nodes from the current depth are processed during that iteration.
Inside the loop, each node is removed from the queue and its children are added for future processing. The key observation is that when i == level_size - 1, we are processing the final node in the current level. Since nodes are processed left to right, this node is the visible rightmost node.
Finally, the collected results are returned.
Go Solution
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func rightSideView(root *TreeNode) []int {
if root == nil {
return []int{}
}
result := []int{}
queue := []*TreeNode{root}
for len(queue) > 0 {
levelSize := len(queue)
for i := 0; i < levelSize; i++ {
node := queue[0]
queue = queue[1:]
if node.Left != nil {
queue = append(queue, node.Left)
}
if node.Right != nil {
queue = append(queue, node.Right)
}
if i == levelSize-1 {
result = append(result, node.Val)
}
}
}
return result
}
The Go implementation follows the same Breadth-First Search logic as the Python version.
Instead of using a deque structure, Go uses a slice to simulate a queue. The front element is removed using:
queue = queue[1:]
Go distinguishes between nil pointers and actual nodes, so child existence checks use:
if node.Left != nil
Unlike Python, Go does not have built-in dynamic lists like deque, but slices provide efficient enough behavior for the problem constraints.
Worked Examples
Example 1
Input:
root = [1,2,3,null,5,null,4]
Tree:
1
/ \
2 3
\ \
5 4
Iteration Trace
| Level | Queue Before Processing | Nodes Processed | Rightmost Node | Result |
|---|---|---|---|---|
| 0 | [1] | 1 | 1 | [1] |
| 1 | [2, 3] | 2, 3 | 3 | [1, 3] |
| 2 | [5, 4] | 5, 4 | 4 | [1, 3, 4] |
Final output:
[1, 3, 4]
Example 2
Input:
root = [1,2,3,4,null,null,null,5]
Tree:
1
/ \
2 3
/
4
/
5
Iteration Trace
| Level | Queue Before Processing | Nodes Processed | Rightmost Node | Result |
|---|---|---|---|---|
| 0 | [1] | 1 | 1 | [1] |
| 1 | [2, 3] | 2, 3 | 3 | [1, 3] |
| 2 | [4] | 4 | 4 | [1, 3, 4] |
| 3 | [5] | 5 | 5 | [1, 3, 4, 5] |
Final output:
[1, 3, 4, 5]
Example 3
Input:
root = [1,null,3]
Tree:
1
\
3
Iteration Trace
| Level | Queue Before Processing | Nodes Processed | Rightmost Node | Result |
|---|---|---|---|---|
| 0 | [1] | 1 | 1 | [1] |
| 1 | [3] | 3 | 3 | [1, 3] |
Final output:
[1, 3]
Example 4
Input:
root = []
The tree is empty, so the algorithm immediately returns:
[]
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | O(n) | Every node is visited exactly once |
| Space | O(n) | The queue may contain an entire tree level |
The algorithm performs a standard Breadth-First Search traversal. Since each node is inserted into and removed from the queue exactly one time, the total work is proportional to the number of nodes.
The space complexity depends on the maximum number of nodes stored simultaneously in the queue. In the worst case, the widest level of the tree may contain O(n) nodes.
Test Cases
from collections import deque
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def rightSideView(self, root):
if not root:
return []
result = []
queue = deque([root])
while queue:
level_size = len(queue)
for i in range(level_size):
node = queue.popleft()
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
if i == level_size - 1:
result.append(node.val)
return result
solution = Solution()
# Example 1
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.right = TreeNode(5)
root.right.right = TreeNode(4)
assert solution.rightSideView(root) == [1, 3, 4] # standard mixed tree
# Example 2
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.left.left = TreeNode(5)
assert solution.rightSideView(root) == [1, 3, 4, 5] # deep left chain
# Example 3
root = TreeNode(1)
root.right = TreeNode(3)
assert solution.rightSideView(root) == [1, 3] # only right children
# Example 4
assert solution.rightSideView(None) == [] # empty tree
# Single node
root = TreeNode(10)
assert solution.rightSideView(root) == [10] # one-node tree
# Left-skewed tree
root = TreeNode(1)
root.left = TreeNode(2)
root.left.left = TreeNode(3)
assert solution.rightSideView(root) == [1, 2, 3] # every node visible
# Right-skewed tree
root = TreeNode(1)
root.right = TreeNode(2)
root.right.right = TreeNode(3)
assert solution.rightSideView(root) == [1, 2, 3] # every node visible
# Tree with negative values
root = TreeNode(-1)
root.left = TreeNode(-2)
root.right = TreeNode(-3)
assert solution.rightSideView(root) == [-1, -3] # handles negatives correctly
# Complete binary tree
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
root.right.left = TreeNode(6)
root.right.right = TreeNode(7)
assert solution.rightSideView(root) == [1, 3, 7] # perfect binary tree
| Test | Why |
|---|---|
| Empty tree | Validates base case handling |
| Single node | Ensures minimal input works |
| Left-skewed tree | Confirms nodes remain visible without right children |
| Right-skewed tree | Confirms straightforward right visibility |
| Complete binary tree | Tests standard multi-level traversal |
| Negative values | Ensures values themselves do not affect logic |
| Mixed structure tree | Verifies correct rightmost selection |
| Deep unbalanced tree | Tests uneven depth handling |
Edge Cases
Empty Tree
An empty tree is represented by root = None. This case is easy to overlook because traversal code usually assumes at least one node exists. Without an early return, attempting to process the queue would lead to errors.
The implementation handles this safely with:
if not root:
return []
This guarantees correct behavior before any traversal begins.
Left-Skewed Tree
A tree that only contains left children can be deceptive because there are no explicit right-side nodes. However, every node is still visible from the right side because no other node blocks it at its depth.
For example:
1
/
2
/
3
The correct result is:
[1, 2, 3]
The BFS traversal naturally handles this because each level contains only one node, making that node both the leftmost and rightmost node.
Unbalanced Trees
Some trees may have one subtree much deeper than another. Naive logic that assumes balanced structure could miss deeper visible nodes.
For example:
1
/ \
2 3
/
4
/
5
Even though the right subtree ends early, nodes 4 and 5 are still visible from the right side at deeper levels.
The level-order traversal correctly processes every depth independently, ensuring no visible node is skipped.
Trees with Missing Children
Binary trees often contain null gaps between nodes. A common bug is attempting to access children without checking whether they exist.
The implementation avoids this by explicitly checking:
if node.left:
and
if node.right:
Only valid child nodes are added to the queue, preventing runtime errors and ensuring correct traversal structure.