Level-Order Traversal

Visit a tree breadth-first with a queue.

Algorithm

The canonical tree is 4(2(1,3),6(5,7)), so this Rust DSA implementation can be compared directly with the rest of the DSA track.

Basic Implementation

basic.rs

use std::collections::VecDeque;
struct Node { value: i32, left: Option<Box<Node>>, right: Option<Box<Node>> }
impl Node {
    fn new(value: i32) -> Self { Self { value, left: None, right: None } }
    fn with(value: i32, left: Node, right: Node) -> Self {
        Self { value, left: Some(Box::new(left)), right: Some(Box::new(right)) }
    }
}
fn render(node: &Option<Box<Node>>) -> String {
    match node {
        None => "_".to_string(),
        Some(n) => {
            if n.left.is_none() && n.right.is_none() { n.value.to_string() }
            else { format!("{}({},{})", n.value, render(&n.left), render(&n.right)) }
        }
    }
}
fn sample_tree() -> Option<Box<Node>> {
    Some(Box::new(Node::with(4, Node::with(2, Node::new(1), Node::new(3)), Node::with(6, Node::new(5), Node::new(7)))))
}
fn list_string(values: &[i32]) -> String {
    format!("[{}]", values.iter().map(|v| v.to_string()).collect::<Vec<_>>().join(", "))
}
fn main() { let root = sample_tree(); let mut output = Vec::new(); let mut queue: VecDeque<&Node> = VecDeque::new(); queue.push_back(root.as_ref().unwrap()); while let Some(node) = queue.pop_front() { output.push(node.value); if let Some(left) = &node.left { queue.push_back(left); } if let Some(right) = &node.right { queue.push_back(right); } } println!("{}", list_string(&output)); }

Complexity

Time: O(n)
Space: O(w) queue space

Implementation notes

Rust stores the tree as Option<Box<Node>>, where child links own subtrees and None represents an empty child.
Level-order traversal uses VecDeque<&Node>: let mut queue: VecDeque<&Node> = VecDeque::new(). The queue holds borrowed node references, not moved Box<Node> values.
The root is enqueued with queue.push_back(root.as_ref().unwrap()); this unwrap is valid for the fixed non-empty sample_tree.
while let Some(node) = queue.pop_front() dequeues borrowed nodes. Values are copied into output: Vec<i32> with output.push(node.value).
Child enqueue logic borrows through the options: if let Some(left) = &node.left { queue.push_back(left); } and the same for right, preserving left-before-right traversal order.
The trace records queue/output states: [4], then output [4] with queue [2, 6], then [4, 2] with [6, 1, 3], then [4, 2, 6] with [1, 3, 5, 7], ending at [4, 2, 6, 1, 3, 5, 7] and an empty queue.
list_string(&output) borrows the result slice, joins display-formatted integers, and println!("{}", ...) prints [4, 2, 6, 1, 3, 5, 7].

level order Level-order traversal uses a queue to visit shallower nodes first.