Problem overview
The function zigzag_traversal receives the root of a binary tree and returns a Vec<Vec<i32>> with one inner vector per level. The first level is read from left to right, the next from right to left, and so on, alternating.
For the tree with root 3, children 9 and 20, and 20's children 15 and 7, the answer is:
[[3], [20, 9], [15, 7]]Level 0 is [3]. Level 1 holds 9 and 20 from left to right, so it is reversed to [20, 9]. Level 2 holds 15 and 7, which is read left to right again.
Approach: collect levels left to right, flip every second one
The usual level-by-level technique is a breadth-first search with a queue. This lesson takes another route that needs no queue. A depth-first search that carries the current level number can still build the lists level by level, as long as it visits the left child before the right child:
- Each call knows its
level. Ifresulthas no list for that level yet, it adds one. - It appends the node's value to
result[level]. - It visits the left subtree, then the right subtree, both with
level + 1.
Within one level, nodes are appended in the order the search reaches them. Because the left subtree is always fully explored before the right one, nodes further left are reached first, so every list ends up in left-to-right order. The zigzag is then a post-processing step: reverse the lists for levels 1, 3, 5 and so on.
The search never skips a level on the way down. Reaching a node at level k means its parent at level k - 1 was visited, and that visit made sure a list existed for level k - 1. So at most one new list is ever needed at a time, when level equals result.len().
Step by step
- Create
resultinzigzag_traversalas a mutableVec<Vec<i32>>holdingvec![], and callSelf::dfs(&root, 0, &mut result). The tree is only read, so it is borrowed with&. The root is on level 0.resultis filled in, so it is borrowed mutably. - Reverse the odd levels: loop with
levelover(1..result.len()).step_by(2), which gives 1, 3, 5 and so on, and callreverse()onresult[level]. - Return
resultas the last expression. - Declare the helper
dfswith the parametersroot: &Option<Box<TreeNode>>,level: usizeandresult: &mut Vec<Vec<i32>>. The level is ausizebecause it is used as an index. - Stop at missing nodes with
if let Some(node) = root. Everything else goes inside this block. - Add a list when the level is new: if
level >= result.len(), push an emptyvec![]. - Store the value:
result[level].push(node.val). - Recurse left with
Self::dfs(&node.left, level + 1, result). - Recurse right the same way with
&node.right. Left must come before right.
The solution in Rust
impl Solution {
fn dfs(root: &Option<Box<TreeNode>>, level: usize, result: &mut Vec<Vec<i32>>) {
if let Some(node) = root {
if level >= result.len() {
result.push(vec![]);
}
result[level].push(node.val);
Self::dfs(&node.left, level + 1, result);
Self::dfs(&node.right, level + 1, result);
}
}
fn zigzag_traversal(root: Option<Box<TreeNode>>) -> Vec<Vec<i32>> {
let mut result: Vec<Vec<i32>> = vec![];
Self::dfs(&root, 0, &mut result);
for level in (1..result.len()).step_by(2) {
result[level].reverse();
}
result
}
}
Rust details that matter here:
- Borrowing instead of moving.
dfstakes&Option<Box<TreeNode>>. Inif let Some(node) = root, matching on a reference givesnodeas a reference too, so nothing is moved out of the tree. The recursive calls use&node.leftand&node.right, which have the same reference type. - Passing
resulton. It is already a&mut Vec<Vec<i32>>, so recursive calls pass it as it is. Rust reborrows it for each call, and it is usable again afterwards. vec![]and inference. The empty vector's type comes from the annotation onresult, andresult.push(vec![])takes its element type from the vector it is pushed into.step_by(2).(1..result.len())is a range ofusize, andstep_by(2)visits every second value from its start. For an empty treeresult.len()is 0, and1..0is an empty range, so the loop doesn't run. It doesn't panic.- Indexing.
result[level]panics iflevelis out of bounds, which is why the list is added before the first access to it. reverse()reverses the inner vector in place and returns nothing, so there is nothing to assign back.
Complexity
Time: O(n). The search visits each node once and does constant work per node. The reversals touch each value in an odd level at most once, so together they cost O(n) too.
Space: O(n). The output holds all n values. The recursion adds O(h) call-stack depth, where h is the height of the tree, which never exceeds n.
Edge cases and common mistakes
- Empty tree. A
Noneroot does nothing indfs, the reversal loop doesn't run, and the result is[]. - Single node. The result is
[[v]], and nothing is reversed. - Missing children. For root 1 with children 2 and 3, where 2 has only a left child 4 and 3 has only a right child 5, the answer is
[[1], [3, 2], [4, 5]]. The lists contain only real nodes, and level 2 keeps 4 before 5 because it is read left to right. - Visiting right before left. Every list would come out in right-to-left order, so the reversal of the odd levels would leave the even levels backwards.
- Reversing the wrong levels. The loop must start at 1. Starting at 0 would flip the even levels instead of the odd ones.
- Forgetting to add a list. Without the check on
level >= result.len(), the first node of each new level indexes past the end and panics.
Testing
- Root 3, children 9 and 20, 20's children 15 and 7:
[[3], [20, 9], [15, 7]]. - Root 1, children 2 and 3, 2's left child 4, 3's right child 5:
[[1], [3, 2], [4, 5]]. - A perfect tree with the values 1 to 15 in level order:
[[1], [3, 2], [4, 5, 6, 7], [15, 14, 13, 12, 11, 10, 9, 8]]. - An empty tree:
[].
