Binary Tree BFS Patterns
Level-order traversal using a queue. The queue gives you explicit access to an entire level at once — enabling zigzag, right-side-view, width, and cousin problems that DFS cannot solve as cleanly.
The Pattern
BFS on a binary tree uses a queue. The queue always contains exactly the nodes of the current level. Process the entire level before adding the next one by recording queue.len() at the start of each outer iteration — that snapshot is the level size. Everything added during this iteration belongs to the next level.
The level boundary is the key invariant. Every BFS tree problem is a variation of: "for each level, do something with the nodes before moving on."
Level Order Traversal
Collect nodes into a Vec<Vec<i32>> where each inner vector is one level. Standard template that all other BFS problems build on.
use std::collections::VecDeque;
#[derive(Debug)]
struct TreeNode { val: i32, left: Option<Box<TreeNode>>, right: Option<Box<TreeNode>> }
fn build(vals: &[Option<i32>]) -> Option<Box<TreeNode>> {
fn helper(vals: &[Option<i32>], i: usize) -> Option<Box<TreeNode>> {
if i >= vals.len() { return None; }
vals[i].map(|v| Box::new(TreeNode {
val: v, left: helper(vals, 2*i+1), right: helper(vals, 2*i+2),
}))
}
helper(vals, 0)
}
fn level_order(root: Option<Box<TreeNode>>) -> Vec<Vec<i32>> {
let mut result = Vec::new();
if root.is_none() { return result; }
let mut queue = VecDeque::new();
queue.push_back(root.unwrap());
while !queue.is_empty() {
let level_size = queue.len();
let mut level = Vec::new();
for _ in 0..level_size {
let node = queue.pop_front().unwrap();
level.push(node.val);
if let Some(l) = node.left { queue.push_back(l); }
if let Some(r) = node.right { queue.push_back(r); }
}
result.push(level);
}
result
}
fn main() {
// 3
// / \
// 9 20
// / \
// 15 7
let tree = build(&[Some(3),Some(9),Some(20),None,None,Some(15),Some(7)]);
println!("{:?}", level_order(tree)); // [[3], [9, 20], [15, 7]]
}Zigzag Level Order Traversal
Alternate the direction each level is added: left-to-right on even levels, right-to-left on odd levels. Collect each level into a VecDeque and conditionally push to front or back.
fn zigzag_level_order(root: Option<Box<TreeNode>>) -> Vec<Vec<i32>> {
let mut result = Vec::new();
if root.is_none() { return result; }
let mut queue = VecDeque::new();
queue.push_back(root.unwrap());
let mut left_to_right = true;
while !queue.is_empty() {
let level_size = queue.len();
let mut level: VecDeque<i32> = VecDeque::new();
for _ in 0..level_size {
let node = queue.pop_front().unwrap();
if left_to_right { level.push_back(node.val); }
else { level.push_front(node.val); }
if let Some(l) = node.left { queue.push_back(l); }
if let Some(r) = node.right { queue.push_back(r); }
}
result.push(level.into_iter().collect());
left_to_right = !left_to_right;
}
result
}
fn main() {
// 3
// / \
// 9 20
// / \
// 15 7
let tree = build(&[Some(3),Some(9),Some(20),None,None,Some(15),Some(7)]);
println!("{:?}", zigzag_level_order(tree));
// [[3], [20, 9], [15, 7]]
}Right Side View
The right side view is the last node at each level. After processing all nodes in a level, the final node seen is the rightmost visible node.
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::new();
queue.push_back(root.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); } // rightmost
if let Some(l) = node.left { queue.push_back(l); }
if let Some(r) = node.right { queue.push_back(r); }
}
}
result
}
fn main() {
// 1
// / \
// 2 3
// \ \
// 5 4
let tree = build(&[Some(1),Some(2),Some(3),None,Some(5),None,Some(4)]);
println!("{:?}", right_side_view(tree)); // [1, 3, 4]
}Average of Levels
Compute the mean of each level's values. Straightforward: sum all values at a level, divide by the level size.
fn average_of_levels(root: Option<Box<TreeNode>>) -> Vec<f64> {
let mut result = Vec::new();
if root.is_none() { return result; }
let mut queue = VecDeque::new();
queue.push_back(root.unwrap());
while !queue.is_empty() {
let level_size = queue.len();
let mut sum = 0i64;
for _ in 0..level_size {
let node = queue.pop_front().unwrap();
sum += node.val as i64;
if let Some(l) = node.left { queue.push_back(l); }
if let Some(r) = node.right { queue.push_back(r); }
}
result.push(sum as f64 / level_size as f64);
}
result
}
fn main() {
// 3
// / \
// 9 20
// / \
// 15 7
let tree = build(&[Some(3),Some(9),Some(20),None,None,Some(15),Some(7)]);
println!("{:?}", average_of_levels(tree)); // [3.0, 14.5, 11.0]
}Maximum Width of Binary Tree
Width is defined as the number of nodes between the leftmost and rightmost non-null nodes on a level, including the nulls in between. Assign index positions: if a node has index i, its left child is 2*i and right child is 2*i+1. Width at each level is last_index - first_index + 1. Normalise indices by subtracting the leftmost index at each level to prevent overflow on deep trees.
fn width_of_binary_tree(root: Option<Box<TreeNode>>) -> usize {
if root.is_none() { return 0; }
let mut queue: VecDeque<(Box<TreeNode>, usize)> = VecDeque::new();
queue.push_back((root.unwrap(), 0));
let mut max_width = 0;
while !queue.is_empty() {
let level_size = queue.len();
let first_idx = queue.front().unwrap().1;
let mut last_idx = 0;
for _ in 0..level_size {
let (node, idx) = queue.pop_front().unwrap();
let idx = idx - first_idx; // normalise to prevent overflow
last_idx = idx;
if let Some(l) = node.left { queue.push_back((l, 2 * idx)); }
if let Some(r) = node.right { queue.push_back((r, 2 * idx + 1)); }
}
max_width = max_width.max(last_idx - 0 + 1);
}
max_width
}
fn main() {
// 1
// / \
// 3 2
// / \ \
// 5 3 9
let tree = build(&[Some(1),Some(3),Some(2),Some(5),Some(3),None,Some(9)]);
println!("{}", width_of_binary_tree(tree)); // 4 (level 2: 5, 3, _, 9)
}Find Largest Value in Each Tree Row
For each level, track the maximum value. A minor variation of level-order traversal.
fn largest_values(root: Option<Box<TreeNode>>) -> Vec<i32> {
let mut result = Vec::new();
if root.is_none() { return result; }
let mut queue = VecDeque::new();
queue.push_back(root.unwrap());
while !queue.is_empty() {
let level_size = queue.len();
let mut level_max = i32::MIN;
for _ in 0..level_size {
let node = queue.pop_front().unwrap();
level_max = level_max.max(node.val);
if let Some(l) = node.left { queue.push_back(l); }
if let Some(r) = node.right { queue.push_back(r); }
}
result.push(level_max);
}
result
}
fn main() {
// 1
// / \
// 3 2
// / \ \
// 5 3 9
let tree = build(&[Some(1),Some(3),Some(2),Some(5),Some(3),None,Some(9)]);
println!("{:?}", largest_values(tree)); // [1, 3, 9]
}Minimum Depth of Binary Tree
The minimum depth is the distance from the root to the nearest leaf. BFS reaches the shallowest leaf first — the first leaf encountered is the answer. DFS would need to explore the entire tree to find the minimum.
fn min_depth(root: Option<Box<TreeNode>>) -> usize {
if root.is_none() { return 0; }
let mut queue = VecDeque::new();
queue.push_back(root.unwrap());
let mut depth = 1;
while !queue.is_empty() {
let level_size = queue.len();
for _ in 0..level_size {
let node = queue.pop_front().unwrap();
if node.left.is_none() && node.right.is_none() { return depth; }
if let Some(l) = node.left { queue.push_back(l); }
if let Some(r) = node.right { queue.push_back(r); }
}
depth += 1;
}
depth
}
fn main() {
// 3
// / \
// 9 20
// / \
// 15 7
let tree = build(&[Some(3),Some(9),Some(20),None,None,Some(15),Some(7)]);
println!("{}", min_depth(tree)); // 2 (root → 9)
// 2
// \
// 3
// \
// 4
let tree2 = build(&[Some(2),None,Some(3),None,None,None,Some(4)]);
println!("{}", min_depth(tree2)); // 3
}