Rust Algorithm Bites – Binary Tree Level Order Traversal
Mastering LeetCode 102: Binary Tree Level Order Traversal with a BFS approach in Rust, leveraging Rc, RefCell, and VecDeque for efficient tree traversal.
Problem Statement
LeetCode 102: Binary Tree Level Order Traversal (link)
Given a binary tree, return its level order traversal as a vector of vectors (i.e. nodes grouped by depth level).
Example:
3
/ \
9 20
/ \
15 7
Output:
[
[3],
[9,20],
[15,7]
]
Algorithm Idea
The problem is about visiting nodes level by level. Two standard approaches exist:
- Iterative BFS with a queue – use a VecDeque to process one level at a time.
- Recursive DFS with level tracking – carry the current depth, and push values into the right bucket.
Both achieve the same result, but BFS is usually clearer for “level order”.
Rust Angle
This is where Rust turns the problem into something more than just “use a queue”:
- Binary trees in Rust aren’t trivial. Because of ownership rules, we wrap child pointers in
Rc<RefCell<TreeNode>>.Rc→ reference counting for shared ownership.RefCell→ interior mutability so we can borrow nodes mutably at runtime.
- With BFS, the main design choice is whether to take ownership of children or just clone references:
take()children → reduces memory use, but mutates the tree.- clone
Rc→ preserves the original tree but uses slightly more memory. - Pattern matching with
Optionis a central Rust idiom here.
First Iteration Solution (Idiomatic BFS)
use std::cell::RefCell;
use std::collections::VecDeque;
use std::rc::Rc;
#[derive(Debug, PartialEq, Eq)]
pub struct TreeNode {
pub val: i32,
pub left: Option<Rc<RefCell<TreeNode>>>,
pub right: Option<Rc<RefCell<TreeNode>>>,
}
impl TreeNode {
#[inline]
pub fn new(val: i32) -> Self {
TreeNode { val, left: None, right: None }
}
}
struct Solution;
impl Solution {
pub fn level_order(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<Vec<i32>> {
let mut result = vec![];
let mut queue = VecDeque::new(); // note: just like vec but providing queue accessors
if let Some(node) = root {
queue.push_back(node); // 1. here we add the root-node to the queue
}
// note: here we process the queue items available, first 1, then 2, then 4 and so on
while !queue.is_empty() {
let n = queue.len();
let mut level = Vec::with_capacity(n);
for _ in 0..n {
if let Some(node) = queue.pop_front() {
let node_ref = node.borrow();
level.push(node_ref.val); // 2. adding the node value to the current level
// todo: process the left and right node as well
}
}
result.push(level); // 3. the current level is added to the result
}
result
}
}
What's going on here?
- takes the first root node and adds it to the queue
- adds the value of the node from the queue to the level result list
- adds the level result list to the overall result list
Let's test this code so far:
#[test]
fn test() {
// [3,9,20,null,null,15,7]
let mut root = TreeNode {
val: 3,
left: Some(Rc::new(RefCell::new(TreeNode {
val: 9,
left: None,
right: None,
}))),
right: Some(Rc::new(RefCell::new(TreeNode {
val: 20,
left: Some(Rc::new(RefCell::new(TreeNode {
val: 15,
left: None,
right: None,
}))),
right: Some(Rc::new(RefCell::new(TreeNode {
val: 7,
left: None,
right: None,
}))),
}))),
};
assert_eq!(
Solution::level_order(Some(Rc::new(RefCell::new(root)))),
vec![vec![3]]
);
}
Ok, this runs green, great.
Now let's go ahead and make the full test green:
#[test]
fn test() {
// .. just as above
assert_eq!(
Solution::level_order(Some(Rc::new(RefCell::new(root)))),
vec![vec![3], vec![9, 20], vec![15, 7]]
);
}
We need to add the left and right child nodes to the queue. The loop will then continue processing the next level. So in other words, batches added to the queue will be processed as the same level. This will then look like this:
// .. all as before
for _ in 0..n {
if let Some(node) = queue.pop_front() {
let node = node.borrow();
level.push(node.val);
// 1. if we got a left node, add it to the queue
if let Some(left) = node.left.as_ref() {
queue.push_back(left.clone());
}
// 2. same for the right node
if let Some(right) = node.right.as_ref() {
queue.push_back(right.clone());
}
}
}
// .. all as before
Full Solution (Idiomatic BFS)
use std::cell::RefCell;
use std::collections::VecDeque;
use std::rc::Rc;
#[derive(Debug, PartialEq, Eq)]
pub struct TreeNode {
pub val: i32,
pub left: Option<Rc<RefCell<TreeNode>>>,
pub right: Option<Rc<RefCell<TreeNode>>>,
}
impl TreeNode {
#[inline]
pub fn new(val: i32) -> Self {
TreeNode { val, left: None, right: None }
}
}
struct Solution;
impl Solution {
pub fn level_order(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<Vec<i32>> {
let mut result = vec![];
let mut queue = VecDeque::new();
if let Some(root) = root {
queue.push_back(root);
}
while !queue.is_empty() {
let n = queue.len();
let mut level = Vec::with_capacity(n);
for _ in 0..n {
if let Some(node) = queue.pop_front() {
let node = node.borrow();
level.push(node.val);
if let Some(left) = node.left.as_ref() {
queue.push_back(left.clone());
}
if let Some(right) = node.right.as_ref() {
queue.push_back(right.clone());
}
}
}
result.push(level);
}
result
}
}
Recursive DFS with level tracking (Bonus Track)
Instead of going Breadth-First, we can also go Depth-First and keep track of the current level. This is a bit more involved, but it’s a good exercise in recursion and managing state.
// .. imports and tree structure as before
impl Solution {
// using recursions
pub fn level_order(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<Vec<i32>> {
let level = 0;
let mut result = vec![];
Self::add_to_level(root, &mut result, level);
result
}
fn add_to_level(root: Option<Rc<RefCell<TreeNode>>>, result: &mut Vec<Vec<i32>>, level: usize) {
if let Some(root) = root.as_ref() {
while result.len() <= level {
result.push(vec![]);
}
// 1. add the current node value to the correct level
// above we make sure the level exists
result[level].push(root.borrow().val);
let next_level = level + 1;
// 3. recurse left with an increased level
let left = root.borrow().left.clone();
Self::add_to_level(left, result, next_level);
// 4. recurse right with an increased level
let right = root.borrow().right.clone();
Self::add_to_level(right, result, next_level);
}
}
}
This approach uses recursion to traverse the tree. The add_to_level function checks if a vector for the current level exists; if not, it creates one. It then recursively processes the left and right children, incrementing the level for each deep dive.
Conclusion
Both BFS and DFS approaches are valid for level order traversal. The BFS approach is often more intuitive for this specific problem, while the DFS approach showcases recursion and state management in Rust. Understanding how to work with Rc and RefCell is crucial when dealing with tree structures in Rust, making this exercise a great way to deepen your Rust skills.
Also VecDeque is a handy data structure in Rust for queue operations, providing efficient push and pop operations from both ends.
Challenge
Extend the solution to handle the following variants:
- Right-to-Left Level Order: Return
[[3],[20,9],[7,15]]instead - Zigzag Level Order: Alternate left-to-right and right-to-left:
[[3],[20,9],[15,7]] - Generic Tree: Make it work with
TreeNode<T>whereT: Clone + Debug
Bonus: Implement a version that works with Box<TreeNode> instead of Rc<RefCell<TreeNode>> and compare the ergonomics.