The challenge
Return one list per depth, alternating left-to-right and right-to-left.
The empty tree returns an empty list. Queue expansion always follows left then right.
Example
Balanced example: [[8], [12, 4], [2, 6, 10, 14]].
Use the walkthrough below to inspect the input and each state change.
See Zigzag, step by step
Follow the branches. Watch the state change.
View child pointers & node state
| Node | Value | Left | Right | State |
|---|---|---|---|---|
| A | 8 | B | C | — |
| B | 4 | D | E | — |
| C | 12 | F | G | — |
| D | 2 | null | null | — |
| E | 6 | null | null | — |
| F | 10 | null | null | — |
| G | 14 | null | null | — |
Inspect the input.
Labels identify node objects; numbers are their values. Left and right child pointers define the tree.
root = A:8View original input
A:8 [L:B, R:C] · B:4 [L:D, R:E] · C:12 [L:F, R:G] · D:2 [L:null, R:null] · E:6 [L:null, R:null] · F:10 [L:null, R:null] · G:14 [L:null, R:null]
Node IDs stay distinct even when values repeat. Pointer mutations update the diagram; removed nodes remain in the state table for reference.
Put it into code
Freeze the queue size before expanding a level.
Nodes store value, left, and right. C++ uses C++17 or later.
from collections import deque
class Node:
def __init__(self, value, left=None, right=None):
self.value = value
self.left = left
self.right = right
def zigzag(root):
if not root:
return []
queue, out = deque([root]), []
reverse = False
while queue:
level = []
for _ in range(len(queue)):
node = queue.popleft()
level.append(node.value)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
if reverse:
level.reverse()
reverse = not reverse
out.append(level)
return out
#include <algorithm>
#include <cmath>
#include <functional>
#include <limits>
#include <map>
#include <optional>
#include <queue>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;
struct Node {
long long value;
Node *left = nullptr, *right = nullptr;
explicit Node(long long v) : value(v) {}
};
vector<vector<long long>> zigzag(Node* root) {
vector<vector<long long>> out;
if (!root) return out;
queue<Node*> pending; pending.push(root);
bool backwards = false;
while (!pending.empty()) {
int width = static_cast<int>(pending.size());
vector<long long> level;
for (int i = 0; i < width; ++i) {
Node* node = pending.front(); pending.pop();
level.push_back(node->value);
if (node->left) pending.push(node->left);
if (node->right) pending.push(node->right);
}
if (backwards) reverse(level.begin(), level.end()); backwards = !backwards;
out.push_back(level);
}
return out;
}