Problem overview
The function right_side_view receives the root of a binary tree, an Option<Box<TreeNode>>, and returns the values you would see standing on the right side of the tree, from the top level to the bottom. The lesson provides TreeNode: it has an i32 field val and two fields left and right, each an Option<Box<TreeNode>>. An empty tree is None and shows nothing, so the answer is an empty vector.
From the right you see exactly one node per level: the rightmost node of that level. For the tree written in level order as [1, 2, 3, None, 5, None, 4], level 0 is 1, level 1 is 2, 3 and level 2 is 5, 4. The rightmost nodes are 1, 3 and 4, so the answer is [1, 3, 4].
The statement sets O(n) time for a tree of n nodes, and O(n) extra space in the worst case.
Approach: visit the tree one level at a time
A tempting shortcut is to follow only right children from the root. It works on the first example, but it fails when the right side of the tree is shorter than the left. For [1, 2, 3, 4] the shortcut gives [1, 3], yet node 4 is visible: it is the only node on its level, and it sits in the left subtree with nothing to its right. The correct answer is [1, 3, 4].
So the question has to be asked level by level: which node is last on each level? A breadth-first search answers it. Keep a queue of the nodes waiting to be visited, with the root in it at the start. At the beginning of each round the queue holds exactly one level. Count its nodes, take them out one at a time from the front, and add each node's children (left first, then right) to the back. Those children are the next level, and they wait behind the rest of this one.
The nodes of a level leave the queue from left to right, so the one taken out last is the rightmost. That is the node you see, and its value goes into the result.
Tracing the first example shows the queue at the start of each round:
level_size = 1, queue = [1]
level_size = 2, queue = [2, 3]
level_size = 2, queue = [5, 4]
The last value of each round, 1, 3 and 4, is the answer. On [1, 2, 3, 4] the last round holds only [4], which is why 4 is reported.
Step by step
- Create the result vector with
Vec::new(). Rust infersVec<i32>from the pushes and from the return type. - Return early on an empty tree.
root.is_none()catches it, and the queue below needs a first node to start from. - Create the queue as a
VecDeque<&TreeNode>and push the root node at the back.as_deref()turns theOption<Box<TreeNode>>into anOption<&TreeNode>, andunwrap()is safe because the tree is not empty here. The queue holds borrowed references, so the tree stays where it is. - Loop while the queue is not empty. Each pass of this loop handles one whole level.
- Store
queue.len()inlevel_size. At this moment the queue holds one level and nothing else. The value must be saved before the inner loop, because the queue grows while the level is processed. - Loop
iover0..level_size. The children added during this loop belong to the next level, and the fixed count keeps the loop from reaching them. - Take the next node with
pop_front().unwrap(). The queue cannot be empty inside the loop, so theOptionis alwaysSome. - Record the last node of the level. When
i == level_size - 1, pushnode.valonto the result. - Queue the left child with
if let Some(left) = node.left.as_deref(), and push it at the back. - Queue the right child the same way, after the left one. This order keeps each level read from left to right.
- Return
resultas the last expression, without a semicolon.
The solution in Rust
use std::collections::VecDeque;
impl Solution {
fn right_side_view(root: Option<Box<TreeNode>>) -> Vec<i32> {
let mut result = Vec::new();
if root.is_none() {
return result;
}
let mut queue: VecDeque<&TreeNode> = VecDeque::new();
queue.push_back(root.as_deref().unwrap());
while !queue.is_empty() {
let level_size = queue.len();
for i in 0..level_size {
let node = queue.pop_front().unwrap();
if i == level_size - 1 {
result.push(node.val);
}
if let Some(left) = node.left.as_deref() {
queue.push_back(left);
}
if let Some(right) = node.right.as_deref() {
queue.push_back(right);
}
}
}
result
}
}
The Rust details worth a closer look:
as_deref(). A node's child is anOption<Box<TreeNode>>. Callingas_deref()on it gives anOption<&TreeNode>, a borrowed look at the node inside the box, with nothing moved or cloned. That is the type the queue stores.- References in the queue. The queue holds
&TreeNode, so every node stays owned by the tree. The tree is not changed while the function runs, so these shared borrows stay valid until the function returns. VecDeque. It is a double-ended queue:push_backandpop_frontboth take constant time. AVecwould also work withremove(0), but that shifts every element and costsO(n)each time.unwrap(). It panics onNone. Here both calls are safe: the root was checked, andpop_frontruns only while the loop counter is below the number of nodes the queue held.level_size - 1with ausize. Subtracting from zero would overflow, butlevel_sizeis at least 1 whenever the inner loop runs, because the outer loop only starts a round with a non-empty queue.- Final expression.
resulthas no semicolon, so it is the value the function returns. The earlyreturn result;covers the empty tree.
Complexity
Time: O(n). Each node enters the queue once and leaves it once, and each operation takes constant time.
Space: O(n). The queue holds at most about two levels at a time, and a level can hold roughly half of all the nodes in a wide tree. The result holds one value per level, which is smaller.
Edge cases and common mistakes
- Empty tree. The early return gives
[]. Without it,unwrap()on the root would panic. - One node. A tree with only the value 7 gives
[7]. - Following only right children. This misses nodes that hang from the left when the right side stops early. On
[1, 2, None, 3, None, 4], a tree that goes down the left side only, it returns[1], while the correct answer is[1, 2, 3, 4]. - Taking the first node of each level. That is the view from the left. On the first example it gives
[1, 2, 5]instead of[1, 3, 4]. - Reading
queue.len()inside the loop. The queue changes as children are added, so the level boundary moves. Save the count inlevel_sizebefore the loop. - Queueing the right child first. Then each level is read right to left, and the last node of the level is the leftmost one.
- Repeated values. Values may repeat. The algorithm works with nodes and positions, not values, so repeats do not matter.
Testing
[1, 2, 3, None, 5, None, 4]gives[1, 3, 4].[1, 2, 3, 4]gives[1, 3, 4].[]gives[].[7]gives[7].[1, 2, None, 3, None, 4]gives[1, 2, 3, 4].[1, 2, 3, 4, 5, 6, 7]gives[1, 3, 7].
