Why this matters
The level-order walk from the level-order lesson reads a tree one level at a time, and each level goes from left to right. Some problems want the direction to change on every level. The output looks like a snake moving down the tree: one level goes right, the next goes left, the next goes right again.
This lesson teaches that pattern in C++ with two methods. The first method builds each level in the normal order and reverses every second level. The second method builds each level in a std::deque, a container that can add items at either end, so the reversed levels need no extra step. Both methods use the same queue, and both are common in interviews.
The idea
Number the levels from the top. The root is level 0, its children are level 1, and so on. The zigzag rule is simple:
- levels 0, 2, 4 and so on go from left to right
- levels 1, 3, 5 and so on go from right to left
Take this tree:
1
/ \
2 3
/ \ \
4 5 6Normal level order gives [1], [2, 3] and [4, 5, 6]. The zigzag order keeps level 0 and level 2 as they are, and reverses level 1. The result is [1], [3, 2] and [4, 5, 6].
The reversal affects only the order of the values inside one level. It does not change which nodes belong to which level. So the job splits into two parts: find the levels, then decide the direction of each one.
The queue does the level split
A queue is a line where the first item added is the first item removed. The level-order walk uses a queue to hold the nodes that are waiting to be visited. Here is the trick that separates the levels. At the start of a level, read the queue's size. That number is how many nodes belong to the current level. Remove exactly that many nodes. Each child you add goes to the back of the queue, so the children wait for the next level.
Trace the tree above with this trick:
| Step | Queue at start of level | Nodes removed | Children added | Level result |
|---|---|---|---|---|
| 1 | 1 | 1 | 2, 3 | [1] |
| 2 | 2 3 | 2, 3 | 4, 5, 6 | [2, 3] |
| 3 | 4 5 6 | 4, 5, 6 | none | [4, 5, 6] |
The queue is empty after step 3, so the walk stops.
Setting up the tree
The examples need a tree to work on. Typing a tree by hand with new and pointers is slow and easy to get wrong, so this lesson builds trees from a list of values in level order. A missing child is marked with std::nullopt, which is C++'s way of saying "no value here". The list {1, 2, 3, 4, 5, std::nullopt, 6} describes the tree above: the node 3 has no left child, and its right child is 6.
Each node owns its children through std::unique_ptr. A unique_ptr is a smart pointer. It deletes the node it holds when the owner goes away, so the examples do not leak memory. The traversal functions only look at nodes, so they take a plain const TreeNode*, which is a pointer that does not own or delete the node.
#include <algorithm>
#include <deque>
#include <iostream>
#include <memory>
#include <optional>
#include <queue>
#include <vector>
struct TreeNode {
int val;
std::unique_ptr<TreeNode> left;
std::unique_ptr<TreeNode> right;
explicit TreeNode(int v) : val(v) {}
};
using NodePtr = std::unique_ptr<TreeNode>;
using Levels = std::vector<std::vector<int>>;
// Builds a tree from level-order values. std::nullopt marks a missing child.
NodePtr build(const std::vector<std::optional<int>>& vals) {
if (vals.empty() || !vals[0]) return nullptr;
NodePtr root = std::make_unique<TreeNode>(*vals[0]);
std::queue<TreeNode*> q;
q.push(root.get());
std::size_t i = 1;
while (!q.empty() && i < vals.size()) {
TreeNode* cur = q.front();
q.pop();
if (i < vals.size() && vals[i]) {
cur->left = std::make_unique<TreeNode>(*vals[i]);
q.push(cur->left.get());
}
++i;
if (i < vals.size() && vals[i]) {
cur->right = std::make_unique<TreeNode>(*vals[i]);
q.push(cur->right.get());
}
++i;
}
return root;
}The builder also uses a queue. It reads the next two values for each node it removes from the queue, and it skips over the std::nullopt entries. You do not need to understand it fully to follow this lesson. It is only there so the examples can describe trees in one line.
Worked example 1: zigzag by reversing
The first method walks the tree the usual way. After each level is collected, the code reverses it when the level is an odd one.
Levels zigzag(const TreeNode* root) {
Levels result;
if (!root) return result;
std::queue<const TreeNode*> q;
q.push(root);
bool left_to_right = true;
while (!q.empty()) {
std::size_t count = q.size(); // how many nodes are in this level
std::vector<int> level;
for (std::size_t k = 0; k < count; ++k) {
const TreeNode* cur = q.front();
q.pop();
level.push_back(cur->val);
if (cur->left) q.push(cur->left.get());
if (cur->right) q.push(cur->right.get());
}
if (!left_to_right) std::reverse(level.begin(), level.end());
result.push_back(std::move(level));
left_to_right = !left_to_right; // flip the direction for the next level
}
return result;
}Read the code in four steps. The if (!root) line handles an empty tree. The count line records the size of the current level before anything is removed. The inner loop collects the level and queues the children. The if (!left_to_right) line reverses the level when the direction is right to left, and the last line flips the direction for the next level.
Run zigzag on the tree from the idea section. The levels it returns are:
[1]
[3, 2]
[4, 5, 6]Level 1 holds 2, 3 in the queue order, and the reversal turns it into 3, 2. Level 2 is not reversed, so it stays 4, 5, 6.
A second example with uneven levels
The tree {3, 9, 20, nullopt, nullopt, 15, 7} has a root of 3, a left child 9, and a right child 20. The node 20 has two children, 15 and 7. Node 9 has no children. The levels are [3], [9, 20] and [15, 7]. The zigzag result is [3], [20, 9] and [15, 7]. The second level is reversed. The third level is not, so it keeps 15 before 7.
The levels have different sizes, and the code does not care. It reads the size of each level from the queue when that level starts. That is why the method works for lopsided trees as well as full ones.
Worked example 2: spiral with a deque
Some problem sets call this order a spiral. The output is the same as the zigzag output, so the two names describe one pattern in this course. The difference is in how the level is built.
The reversal method builds the level left to right and then reverses it, which means touching every value twice. A deque can avoid the second step. A deque, short for double-ended queue, lets you add to the front with push_front and to the back with push_back, and both cost the same small amount of work.
On a right-to-left level, the nodes are still visited in the same order: left to right in the tree. If each node goes to the front of the deque, the last node visited ends up first. Here is level 1 of the example tree:
| Node visited | Action | Deque after the action |
|---|---|---|
2 | push_front(2) | 2 |
3 | push_front(3) | 3 2 |
The deque now holds the level in the right-to-left order without any reversing. The code for the spiral follows the same structure as the zigzag code.
Levels spiral(const TreeNode* root) {
Levels result;
if (!root) return result;
std::queue<const TreeNode*> q;
q.push(root);
bool left_to_right = true;
while (!q.empty()) {
std::size_t count = q.size();
std::deque<int> level;
for (std::size_t k = 0; k < count; ++k) {
const TreeNode* cur = q.front();
q.pop();
if (left_to_right) {
level.push_back(cur->val);
} else {
level.push_front(cur->val);
}
if (cur->left) q.push(cur->left.get());
if (cur->right) q.push(cur->right.get());
}
result.emplace_back(level.begin(), level.end());
left_to_right = !left_to_right;
}
return result;
}The queue still walks the nodes in level order, and the children still go to the back of the queue. The only change is where each value lands in the level. The last line of the loop copies the finished deque into a std::vector<int>, because the result type uses vectors.
Which method should you pick? In an interview, either is correct. The reversal method is easier to explain, because each step is a plain reverse. The deque method is a good habit for problems where you want to build a sequence in place and avoid a second pass.
Worked example 3: edge cases
Good code handles the smallest inputs. There are three cases to check.
The empty tree has no root. Both functions return an empty list of levels before the loop starts. The line if (!root) return result; handles this case.
The single node tree {42} has one level with one value. The loop runs once. The level is [42], and reversing a list with one item changes nothing.
A chain is a tree where each node has only one child. The input {1, 2, std::nullopt, 3, std::nullopt, 4} is a chain that goes down the left side: 1, then 2, then 3, then 4. Every level has exactly one node, so the direction of each level does not matter. The output has four levels:
[1]
[2]
[3]
[4]This case is useful because it shows that the direction flag keeps flipping even when a reversal does nothing. The code does not need a special case for it.
Putting the examples together
The program below runs the three examples and prints the results with a helper function. The helper is only for display, and the output is what the program prints.
void print(const char* name, const Levels& levels) {
std::cout << name << ":\n";
for (const auto& level : levels) {
std::cout << " [";
for (std::size_t i = 0; i < level.size(); ++i) {
if (i) std::cout << ", ";
std::cout << level[i];
}
std::cout << "]\n";
}
}
int main() {
using std::nullopt;
NodePtr t1 = build({1, 2, 3, 4, 5, nullopt, 6});
print("zigzag t1", zigzag(t1.get()));
print("spiral t1", spiral(t1.get()));
NodePtr t2 = build({3, 9, 20, nullopt, nullopt, 15, 7});
print("zigzag t2", zigzag(t2.get()));
print("spiral t2", spiral(t2.get()));
NodePtr t3 = build({});
print("zigzag empty", zigzag(t3.get()));
print("spiral empty", spiral(t3.get()));
NodePtr t4 = build({1, 2, nullopt, 3, nullopt, 4});
print("zigzag chain", zigzag(t4.get()));
print("spiral chain", spiral(t4.get()));
return 0;
}Compile and run it with:
g++ -std=c++20 -Wall -Wextra -g zigzag.cpp -o zigzag && ./zigzagThe output is:
zigzag t1:
[1]
[3, 2]
[4, 5, 6]
spiral t1:
[1]
[3, 2]
[4, 5, 6]
zigzag t2:
[3]
[20, 9]
[15, 7]
spiral t2:
[3]
[20, 9]
[15, 7]
zigzag empty:
spiral empty:
zigzag chain:
[1]
[2]
[3]
[4]
spiral chain:
[1]
[2]
[3]
[4]The empty tree prints its label with no levels under it. The two methods agree on every input, which is what you expect when they describe the same order.
Common mistakes
Reading the level size inside the loop
The most common bug is to write the loop as for (k = 0; k < q.size(); ++k). The queue shrinks each time a node is removed and grows each time a child is added, so the bound changes while the loop runs. The code compiles and runs, and it gives the wrong answer with no error message.
The tree {1, 2, 3, 4, 5, nullopt, 6} shows the problem. The buggy version prints these level sizes:
level size 3
level size 2
level size 1The correct sizes are 1, 2 and 3. The fix is to read the size once into a variable before the loop, as the count line in the examples does. The corrected version prints:
level size 1
level size 2
level size 3Forgetting to flip the direction
If the flag never changes, every level goes left to right, and the output is the same as the normal level order. The tree {1, 2, 3, 4, 5, nullopt, 6} prints [1], [2, 3] and [4, 5, 6] with no flip. Check that the flag changes at the end of every level, not inside the inner loop, where it would flip once per node.
Pushing null children
A nullptr in the queue is a bug waiting to happen. The code must check if (cur->left) before it pushes the child. If the check is missing, the next pass removes a null pointer and reads cur->val from it. Without a sanitizer, the program stops with exit code 139, which means it was killed by a segmentation fault. Build with AddressSanitizer, a checker built into g++ that reports bad memory use while the program runs, to see where the crash happens:
g++ -std=c++20 -g -fsanitize=address mistakes.cpp -o mistakes_asan
./mistakes_asanThe sanitizer prints a report like this one, trimmed:
==594132==ERROR: AddressSanitizer: SEGV on unknown address 0x000000000000 (pc ...)
==594132==The signal is caused by a READ memory access.
==594132==Hint: address points to the zero page.
#0 ... in push_nulls(TreeNode const*) mistakes.cpp:46The address 0x000000000000 is the null pointer. The line number points to the line that read a field of it, so it will differ in your file.
Calling std::reverse on the wrong level
If a spiral result is built with push_front and then reversed again, the odd levels are put back in the wrong order. Choose one method for each level and do not mix them.
Practice
Exercise 1. Give the zigzag output for the perfect tree {1, 2, 3, 4, 5, 6, 7}. The root is 1, its children are 2 and 3, and the leaves are 4, 5, 6 and 7 from left to right.
Show the answer
The output has three levels: [1], then [3, 2] because level 1 is reversed, then [4, 5, 6, 7] because level 2 keeps its order. Both methods give the same result.
Exercise 2. Give the zigzag output for {1, 2, 3, std::nullopt, 4}. Node 2 has no left child and a right child 4. Node 3 has no children.
Show the answer
The levels are [1], [2, 3] and [4]. Level 1 is reversed to [3, 2]. Level 2 contains only 4, so it stays [4]. The output is [1], [3, 2] and [4].
Exercise 3. The chain {1, 2, std::nullopt, 3, std::nullopt, 4} has four levels. Predict the output of zigzag for it without running the code.
Show the answer
The output is [1], [2], [3] and [4], one value per line. Each level has one node, so a reversal changes nothing.
Exercise 4. The spiral function never calls std::reverse. Explain in your own words how it still gives the right-to-left order on odd levels.
Show the answer
On an odd level, each node is put at the front of the deque with push_front. The nodes are visited left to right, so each new node goes in front of the ones before it. The last node visited ends up first, which is the right-to-left order. The deque builds the reversed order directly.
Exercise 5. The function below has the bug from the common mistakes section. Fix it so that it prints the level sizes 1, 2 and 3 for the tree {1, 2, 3, 4, 5, std::nullopt, 6}.
void level_sizes(const TreeNode* root) {
std::queue<const TreeNode*> q;
q.push(root);
while (!q.empty()) {
std::vector<int> level;
for (std::size_t k = 0; k < q.size(); ++k) {
const TreeNode* cur = q.front();
q.pop();
level.push_back(cur->val);
if (cur->left) q.push(cur->left.get());
if (cur->right) q.push(cur->right.get());
}
std::cout << "level size " << level.size() << "\n";
}
}Show the answer
Read the size once before the loop. Replace the loop header with this code:
std::size_t count = q.size();
for (std::size_t k = 0; k < count; ++k) {The bound is now fixed for the whole level. The output is level size 1, level size 2 and level size 3.
Summary
- Zigzag order reads the levels from top to bottom and flips the direction on every level, starting with left to right at the root.
- Read the queue size once at the start of each level. That count is what separates one level from the next.
- Reversing a level with
std::reverseand building it withpush_frontin astd::dequegive the same output. - Empty trees, single nodes and chains need no special code if the direction flag is handled correctly.
- Most bugs in this pattern come from reading the queue size inside the loop or pushing null children.