Problem overview
Level order traversal lists a binary tree's values level by level, each level from left to right. For the tree with root 3, children 9 and 20, and 20's children 15 and 7, the result is [[3], [9, 20], [15, 7]].
In this lesson the tree arrives as a table of child indices. The nodes are numbered, a node's value is its number, and links is a vector of [usize; 2] pairs where links[v] holds the left and right child of node v. The index 0 means "no child", which is why node numbers start at 1 and the table has n + 1 entries. For each test case the program prints one line per level, with the values separated by single spaces.
The parsing code and the loop that builds links are already written in the starter code. The learner writes the traversal and the code that prints the levels.
Approach: a depth-first search that remembers the depth
Level order is usually done breadth-first, with a queue. A depth-first search can produce the same result, as long as every node knows its depth. Keep a vector of levels, result. When the search reaches a node at depth level, append the node's value to result[level]. If that is the first node found at that depth, the row doesn't exist yet, so create it first.
Visiting the left child before the right child keeps each row in left-to-right order. Take the example: the search goes 3, then 9 (row 1 is created), then back up to 20 (appended to row 1), then 15 (row 2 is created), then 7. The rows come out as [3], [9, 20] and [15, 7].
Step by step
- Declare
resultas a mutableVec<Vec<i32>>, one inner vector per level. - Start the search from the root only if
root_valis greater than 0, since 0 means the tree is empty. The call isSelf::dfs_impl(root_val, 0, &links, &mut result): the root is at level 0, the table is borrowed, and the result is borrowed mutably. - Print the levels. Loop over
&resultso the vector is borrowed, not moved. For eachlevel_vals, turn the numbers into strings withiter().map(...).collect(), join them with a space, and append the line plus a newline toout. - Declare
dfs_impl. It takesnodeandlevelasusize,linksas&[[usize; 2]]andresultas&mut Vec<Vec<i32>>. It returns nothing. - Create the row when the search goes deeper than ever before. If
level >= result.len(), push an empty vector. - Record the node. Push
node as i32ontoresult[level]. The node's number is its value, andasconverts theusize. - Read the children from
links[node]: position 0 is the left child and position 1 the right. - Recurse on each existing child with
level + 1, left first. A child index of 0 is skipped.
The solution in Rust
use std::sync::OnceLock;
static LOT_DONE: OnceLock<()> = OnceLock::new();
impl Solution {
fn dfs_impl(node: usize, level: usize, links: &[[usize; 2]], result: &mut Vec<Vec<i32>>) {
if level >= result.len() {
result.push(Vec::new());
}
result[level].push(node as i32);
let left = links[node][0];
let right = links[node][1];
if left > 0 {
Self::dfs_impl(left, level + 1, links, result);
}
if right > 0 {
Self::dfs_impl(right, level + 1, links, result);
}
}
fn dfs(_nums: Vec<i32>) {
LOT_DONE.get_or_init(|| {
let input = std::fs::read_to_string("p1.in").unwrap();
let toks: Vec<usize> = input
.split_whitespace()
.map(|s| s.parse::<usize>().unwrap())
.collect();
let mut idx = 0usize;
let t = toks[idx];
idx += 1;
let mut out = String::new();
for _ in 0..t {
let n = toks[idx];
idx += 1;
let edges = toks[idx];
idx += 1;
let root_val = toks[idx];
idx += 1;
let mut links = vec![[0usize; 2]; n + 1];
for _ in 0..edges {
let v = toks[idx];
idx += 1;
let l = toks[idx];
idx += 1;
let r = toks[idx];
idx += 1;
links[v] = [l, r];
}
let mut result: Vec<Vec<i32>> = Vec::new();
if root_val > 0 {
Self::dfs_impl(root_val, 0, &links, &mut result);
}
for level_vals in &result {
let line: Vec<String> = level_vals.iter().map(|v| v.to_string()).collect();
out.push_str(&line.join(" "));
out.push('\n');
}
}
std::fs::write("p1.out", out).unwrap();
});
}
}
The Rust details worth a closer look:
- Index 0 as "no node". The table is built with
vec![[0usize; 2]; n + 1], so every node starts with the pair[0, 0]: no children. Only nodes that appear in an edge line get real children. Using 0 as the sentinel works because ausizecan't be negative, and node numbers start at 1. - Slices and arrays.
linksis passed as&[[usize; 2]], a borrowed slice of two-element arrays. Passing&links, a reference to aVec, works because Rust converts it to a slice automatically. - References are passed on unchanged. Inside
dfs_impl,linksandresultare already references, so the recursive calls pass them without another&or&mut. as i32. Castingusizetoi32truncates silently if the number doesn't fit. Node numbers here are small, so it is safe.- Borrowing while looping.
for level_vals in &resultgives references to the rows. Looping overresultitself would move it. mapandcollect. The annotationVec<String>tellscollectwhat to build.join(" ")works on a vector of strings and puts one space between neighbours, with none at the end.push_strandpush.push_strappends a string slice andpushappends onechar, here'\n'.
Complexity
Time: O(n) per test case. Each node is visited once, and the work per node is constant: a possible row creation, one push and two table lookups. Printing touches each value once.
Space: O(n). The table has n + 1 pairs and the result holds each value once. The recursion adds O(h) stack frames for a tree of height h, which is at most n for a chain.
Edge cases and common mistakes
- Empty tree. With
root_valequal to 0, the search is never started and nothing is printed for that test case. - One node. It prints one line with that node's number.
- Visiting the right child first. Each row would come out right to left.
- Creating a row for every node. The row is created only when
level >= result.len(). Doing it on every visit would give each node its own row. - Forgetting the
left > 0andright > 0checks. A call with node 0 would record a node that doesn't exist and read the pair that belongs to the "no node" entry, which is[0, 0], so the search would call itself on 0 forever and overflow the stack. - Missing newline after each level. All the levels would end up on one line.
Testing
- Node 1 with children 2 and 3, and node 3 with children 4 and 5: prints the lines
1,2 3and4 5. - A test case with 3 nodes, no edges and a root of 0: prints nothing.
