Binary Tree Right Side View
Problem
Given the root of a binary tree, return the values of the nodes visible from the right side, ordered from top to bottom.
- The number of nodes in the tree is in the range [0, 100]
- −100 ≤ Node.val ≤ 100
Example
root = [1,2,3,null,5,null,4][1,3,4]The tree structure is: 1 / \ 2 3 \ \ 5 4 A brute-force approach would be to traverse the tree and record all nodes at each level, then pick the rightmost node. The algorithm uses a breadth-first search (BFS) to traverse level by level. At each level, it processes all nodes, updating the rightmost node seen. For the example, at level 0, node 1 is the only node and thus the rightmost. At level 1, nodes 2 and 3 are processed; 3 is the rightmost. At level 2, nodes 5 and 4 are processed; 4 is the rightmost. Collecting these rightmost nodes yields [1,3,4].
Approach
Straightforward Solution
A naive approach would be to perform a DFS and track the rightmost node at each depth, but this requires careful state management and can be less intuitive.
Core Observation
The right side view of a binary tree corresponds to the rightmost node at each depth level when traversed level by level.
Path to Optimal
Recognizing that BFS naturally processes nodes level by level, the algorithm uses a queue to traverse the tree breadth-first. At each level, the last node processed is the rightmost node visible from that level. By recording this node's value, the algorithm efficiently constructs the right side view.
Optimal Approach
Use a queue initialized with the root node. For each level, iterate over all nodes currently in the queue, updating a variable to track the last node processed. Enqueue the children of each node for the next level. After processing the level, append the last node's value to the result list. Continue until the queue is empty. This guarantees an O(n) time complexity and O(n) space complexity.
Time
O(n)
Each node is enqueued and dequeued exactly once during the BFS traversal, resulting in linear time proportional to the number of nodes.
Space
O(n)
The queue can hold up to the maximum number of nodes at any level, which in the worst case is proportional to n/2 (for a balanced tree), resulting in O(n) auxiliary space.
Pattern Spotlight
BFS (Level-Order Traversal for Layered State Exploration)
When a problem requires information about nodes at each depth or layer, use BFS to process nodes level by level, enabling direct access to the first or last node at each level without complex state tracking.
Solution
| 1 | import collections
|
| 2 |
|
| 3 | class Solution:
|
| 4 | def rightSideView(self, root: TreeNode) -> list[int]:
|
| 5 | res = []
|
| 6 | if not root:
|
| 7 | return res
|
| 8 |
|
| 9 | q = collections.deque([root])
|
| 10 |
|
| 11 | while q:
|
| 12 | right_side = None
|
| 13 | q_len = len(q)
|
| 14 |
|
| 15 | for i in range(q_len):
|
| 16 | node = q.popleft()
|
| 17 | if node:
|
| 18 | right_side = node
|
| 19 | q.append(node.left)
|
| 20 | q.append(node.right)
|
| 21 |
|
| 22 | if right_side:
|
| 23 | res.append(right_side.val)
|
| 24 |
|
| 25 | return res |
| 1 | class Solution { |
| 2 | public List<Integer> rightSideView(TreeNode root) { |
| 3 | List<Integer> res = new ArrayList<>(); |
| 4 | if (root == null) { |
| 5 | return res; |
| 6 | } |
| 7 | |
| 8 | Queue<TreeNode> q = new ArrayDeque<>(); |
| 9 | q.offer(root); |
| 10 | |
| 11 | while (!q.isEmpty()) { |
| 12 | TreeNode rightSide = null; |
| 13 | int size = q.size(); |
| 14 | |
| 15 | for (int i = 0; i < size; i++) { |
| 16 | TreeNode node = q.poll(); |
| 17 | if (node != null) { |
| 18 | rightSide = node; |
| 19 | if (node.left != null) { |
| 20 | q.offer(node.left); |
| 21 | } |
| 22 | if (node.right != null) { |
| 23 | q.offer(node.right); |
| 24 | } |
| 25 | } |
| 26 | } |
| 27 | |
| 28 | if (rightSide != null) { |
| 29 | res.add(rightSide.val); |
| 30 | } |
| 31 | } |
| 32 | |
| 33 | return res; |
| 34 | } |
| 35 | } |
Step-by-Step Solution
Initialize Result List Before BFS Traversal
| 5 | res = []
|
Objective
To create the output list that will store the visible rightmost node value from each level.
Key Insight
The BFS loop determines one visible node per level, but those values need a stable container from the start. Initializing the result list before any queue logic makes the output flow explicit and also supports the empty-tree case cleanly.
Interview Quick-Check
Core Logic
Create the result list before traversal so each completed level can append one visible value.
State & Boundaries
The result container must exist even when the tree is empty, because the empty-tree case returns it directly.
Return Empty List for Empty Tree
| 6 | if not root:
|
| 7 | return res
|
Objective
To handle the edge case where the input tree is empty by returning an empty result immediately.
Key Insight
Checking for an empty root upfront prevents unnecessary processing and avoids errors from operating on a null tree. This early exit is a standard defensive programming practice that simplifies the main logic by guaranteeing the root exists thereafter.
Interview Quick-Check
State & Boundaries
Return immediately if root is None, as no nodes are visible from the right side.
Traverse Tree Level-by-Level Using a Queue
| 9 | q = collections.deque([root])
|
| 11 | while q:
|
| 12 | right_side = None
|
| 13 | q_len = len(q)
|
| 15 | for i in range(q_len):
|
| 16 | node = q.popleft()
|
| 17 | if node:
|
| 18 | right_side = node
|
| 19 | q.append(node.left)
|
| 20 | q.append(node.right)
|
| 22 | if right_side:
|
| 23 | res.append(right_side.val)
|
Objective
To perform a breadth-first search that processes nodes level by level, tracking the rightmost node at each level.
Key Insight
BFS naturally groups nodes by depth, allowing the algorithm to identify the rightmost node by updating a variable during the iteration over each level's nodes. Enqueuing children ensures the next level is ready for processing. This approach avoids complex recursion or additional data structures to track node positions.
Interview Quick-Check
Core Logic
Use a queue to process nodes level by level, updating the rightmost node variable as nodes are dequeued.
State & Boundaries
At each level, process exactly the number of nodes currently in the queue to isolate levels.
Common Pitfalls & Bugs
Appending None children to the queue can cause unnecessary processing; checking node existence before enqueueing children avoids this.
Complexity
Each node is enqueued and dequeued once, ensuring O(n) time and space complexity.
Return the Collected Right Side View
| 25 | return res |
Objective
To return the list of rightmost node values collected from each level after BFS completes.
Key Insight
After processing all levels, the result list contains exactly one node per level: the rightmost visible node. Returning this list completes the solution.
Interview Quick-Check
Core Logic
Returning the accumulated list of rightmost nodes provides the final right side view.
Line Analysis
This solution has 1 Critical line interviewers watch for.
right_side = nodeUpdate the rightmost node to the current node.
This assignment is critical because it captures the rightmost node at the current level; updating it for every valid node ensures the last one processed is the visible node from the right side.
q = collections.deque([root])Initialize a queue with the root node for BFS traversal.
The queue is the fundamental data structure enabling level-order traversal, starting with the root as the first node to process.
node = q.popleft()Remove the next node from the queue for processing.
Dequeuing nodes in FIFO order ensures BFS processes nodes level by level from left to right.
if right_side:If a rightmost node was found at this level, append its value to the result list.
Appending the rightmost node's value after processing the entire level ensures the result captures the visible node from the right side at that depth.
return resReturn the list of rightmost node values after BFS completes.
Returning the accumulated list provides the final answer representing the right side view of the binary tree.
if not root:Check if the root is None (empty tree).
This early check prevents unnecessary processing and ensures the algorithm handles the edge case of an empty tree gracefully.
return resReturn an empty list if the tree is empty.
Returning immediately avoids errors and correctly represents that no nodes are visible from the right side in an empty tree.
right_side = NoneInitialize a variable to track the rightmost node at the current level.
Resetting this variable at each level allows capturing the last node processed, which corresponds to the rightmost node visible from that level.
q_len = len(q)Record the number of nodes at the current level.
Knowing the level size allows processing exactly one level's nodes per iteration, isolating levels in the BFS traversal.
if node:Check if the dequeued node is not None.
This check prevents processing null nodes, avoiding errors and unnecessary queue insertions.
q.append(node.left)Add the left child of the current node to the queue.
Enqueuing the left child prepares the next level for BFS traversal, ensuring all nodes are eventually processed.
q.append(node.right)Add the right child of the current node to the queue.
Enqueuing the right child alongside the left child maintains the correct BFS order and completeness of traversal.
res.append(right_side.val)Add the rightmost node's value to the output list.
This line finalizes the capture of the right side view for the current level, building the final output incrementally.
while q:Continue processing while there are nodes in the queue.
The loop ensures all levels are processed until no nodes remain, enabling complete traversal of the tree.
for i in range(q_len):Iterate over all nodes at the current level.
This loop processes each node in the current level, enabling the algorithm to identify the rightmost node and enqueue children for the next level.
res = []Initialize the output list that will store the right-side view.
The result list accumulates exactly one visible node value per level, so it must exist before any empty-tree return or BFS processing begins.
Test Your Understanding
Why does the BFS approach guarantee that the last node processed at each level is the rightmost visible node?
Because BFS processes nodes in order from left to right at each level, the last node dequeued at that level is the rightmost node, which is exactly the node visible from the right side.
Related Problems
BFS pattern
Don't just read it. Drill it.
Reconstruct Binary Tree Right Side View from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Binary Tree Right Side View drill