Binary Tree Zigzag Level Order Traversal solution and explanation
Google
9 more videos on this problem
Binary Tree Zigzag Level Order Traversal - Leetcode 103 - PythonNeetCodeIO · 8:00 · 30K views
Zig Zag Traversal (LeetCode 103) | Full Solution with visuals and a little trick | Study AlgorithmsNikhil Lohia · 15:11 · 20K views
Binary Tree Zigzag Level Order Traversal | LeetCode 103 | C++Knowledge Center · 16:38 · 14K views
Binary Tree Zigzag Level Order Traversal - LeetCode 103 PythonDeepti Talesra · 8:32 · 10K views
LEETCODE 103 (JAVASCRIPT) | BINARY TREE ZIGZAG LEVEL ORDER TRAVERSALAndy Gala · 9:27 · 2K views
Binary Tree Zigzag Level Order Traversal | Leet code 103 | Theory explained + Python codeSai Anish Malla · 5:34 · 1K views
103. Binary Tree Zigzag Level Order Traversal - JAVA (BFS)Sourin Majumdar · 6:17 · 745 views
Binary Tree Zigzag Level Order Traversal | LeetCode 103Michael Vandi · 10:55 · 735 views
Binary Tree Zigzag Level Order | LeetCode 103Destination FAANG · 15:44 · 666 views
Leetcode 103 Binary Tree Zigzag Level Order Traversal | Amazon Google | SDE Sheet belowCoding Decoded · 12:24 · 665 views
The problem
Given the root of a binary tree, return the zigzag level order traversal of its nodes' values. (i.e., from left to right, then right to left for the next level and alternate between).
Example 1:
Input: root = [3,9,20,null,null,15,7] Output: [[3],[20,9],[15,7]]
Example 2:
Input: root = [1] Output: [[1]]
Example 3:
Input: root = [] Output: []
Constraints:
- The number of nodes in the tree is in the range
[0, 2000]. -100 <= Node.val <= 100
Approach overview
Problem Overview: Given the root of a binary tree, return the level order traversal of its nodes where the direction alternates on every level. The first level is left-to-right, the next right-to-left, then left-to-right again, forming a zigzag pattern.
Approach 1: Breadth-First Search with Direction Toggle (O(n) time, O(n) space)
This approach performs a standard Breadth-First Search using a queue to process the tree level by level. For each level, collect node values in an array. Maintain a boolean flag that tracks traversal direction. When the flag indicates right-to-left, reverse the collected level values before adding them to the result (or insert at the front while building the level). Every node is visited exactly once, so the time complexity is O(n), and the queue plus result storage requires O(n) space.
The key insight is that zigzag order does not require changing the traversal itself. The queue still processes nodes left-to-right. Only the way values are stored for each level changes. This makes the implementation simple and reliable for any Tree or Binary Tree level traversal problem.
Approach 2: Depth-First Search with Depth Registration (O(n) time, O(n) space)
This approach uses recursive DFS while tracking the current depth. Maintain a list of lists where each index represents a level. When visiting a node, check the depth: if the level does not exist yet, create a new list. For even depths, append the value normally; for odd depths, insert the value at the beginning of the list. This produces the zigzag order during traversal without reversing later.
DFS explores nodes using recursion but still ensures every node is processed exactly once. The recursion stack can grow up to the tree height, giving O(h) stack usage, while the result structure stores all nodes for O(n) total space.
Recommended for interviews: The BFS solution is the most common and expected answer. Interviewers want to see that you recognize this as a level-order traversal problem and apply a direction toggle. DFS with depth tracking shows deeper understanding of tree traversal patterns, but BFS is typically clearer and easier to implement under interview time constraints.
Approach 1: Breadth-First Search with Direction Toggle
This approach leverages the standard Breadth-First Search (BFS) algorithm to perform a level order traversal. We use a queue to traverse the tree level-by-level. For each level, we determine the order (left-to-right or right-to-left) by toggling a flag. At odd levels, we simply reverse the order of elements collected from the queue to achieve the zigzag effect.
from collections import deque
from typing import List, Optional
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
if not root:
return []
results = []
queue = deque([root])
left_to_right = True
while queue:
level = deque()
for i in range(len(queue)):
node = queue.popleft()
if left_to_right:
level.append(node.val)
else:
level.appendleft(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
results.append(list(level))
left_to_right = not left_to_right
return resultsimport java.util.*;
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
public class Solution {
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
List<List<Integer>> result = new ArrayList<>();
if (root == null) return result;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
boolean leftToRight = true;
while (!queue.isEmpty()) {
int size = queue.size();
List<Integer> levelList = new ArrayList<>(size);
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll();
if (leftToRight) {
levelList.add(node.val);
} else {
levelList.add(0, node.val);
}
if (node.left != null) queue.offer(node.left);
if (node.right != null) queue.offer(node.right);
}
result.add(levelList);
leftToRight = !leftToRight;
}
return result;
}
}#include <iostream>
#include <vector>
#include <deque>
using namespace std;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
vector<vector<int>> result;
if (!root) return result;
deque<TreeNode*> q;
q.push_back(root);
bool leftToRight = true;
while (!q.empty()) {
int size = q.size();
vector<int> row(size);
for (int i = 0; i < size; ++i) {
TreeNode* node = q.front();
q.pop_front();
int index = (leftToRight) ? i : (size - 1 - i);
row[index] = node->val;
if (node->left) q.push_back(node->left);
if (node->right) q.push_back(node->right);
}
leftToRight = !leftToRight;
result.push_back(row);
}
return result;
}var zigzagLevelOrder = function(root) {
if (!root) return [];
const result = [];
const queue = [root];
let leftToRight = true;
while (queue.length > 0) {
const size = queue.length;
const levelNodes = [];
for (let i = 0; i < size; i++) {
const node = queue.shift();
if (leftToRight) {
levelNodes.push(node.val);
} else {
levelNodes.unshift(node.val);
}
if (node.left) queue.push(node.left);
if (node.right) queue.push(node.right);
}
result.push(levelNodes);
leftToRight = !leftToRight;
}
return result;
};#include <stdio.h>
#include <stdlib.h>
// Definition for a binary tree node.
typedef struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
void reverse(int* arr, int left, int right) {
while (left < right) {
int temp = arr[left];
arr[left++] = arr[right];
arr[right--] = temp;
}
}
int** zigzagLevelOrder(TreeNode* root, int** columnSizes, int* returnSize) {
if (!root) {
*returnSize = 0;
return NULL;
}
int** result = (int**) malloc(2000 * sizeof(int*));
int* sizes = (int*) malloc(2000 * sizeof(int));
*returnSize = 0;
TreeNode** queue = (TreeNode**) malloc(2000 * sizeof(TreeNode*));
int front = 0, rear = 0;
queue[rear++] = root;
int level = 0;
while (front < rear) {
int count = rear - front;
int* levelVals = (int*) malloc(count * sizeof(int));
for (int i = 0; i < count; ++i) {
TreeNode* node = queue[front++];
levelVals[i] = node->val;
if (node->left) queue[rear++] = node->left;
if (node->right) queue[rear++] = node->right;
}
if (level % 2 == 1) {
reverse(levelVals, 0, count - 1);
}
result[*returnSize] = levelVals;
sizes[*returnSize] = count;
(*returnSize)++;
level++;
}
*columnSizes = sizes;
free(queue);
return result;
}using System;
using System.Collections.Generic;
public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int x) { val = x; }
}
public class Solution {
public IList<IList<int>> ZigzagLevelOrder(TreeNode root) {
IList<IList<int>> results = new List<IList<int>>();
if (root == null) return results;
Queue<TreeNode> queue = new Queue<TreeNode>();
queue.Enqueue(root);
bool leftToRight = true;
while (queue.Count > 0) {
int size = queue.Count;
LinkedList<int> levelNodes = new LinkedList<int>();
for (int i = 0; i < size; i++) {
var node = queue.Dequeue();
if (leftToRight) {
levelNodes.AddLast(node.val);
} else {
levelNodes.AddFirst(node.val);
}
if (node.left != null) queue.Enqueue(node.left);
if (node.right != null) queue.Enqueue(node.right);
}
results.Add(new List<int>(levelNodes));
leftToRight = !leftToRight;
}
return results;
}
}The Python solution uses deque for both the queue and level list operations to efficiently achieve the zigzag pattern. The toggle mechanism allows levels to be appended left-to-right or right-to-left without compromising on runtime efficiency.
Time Complexity: O(n), where n represents the number of nodes.
Space Complexity: O(n), primarily due to the result list and BFS queue space requirements.
Approach 2: Depth-First Search with Depth Registration
In contrast to the BFS method, this approach utilizes Depth-First Search (DFS) for traversal. Recursive calls are made to process each node, and a hashmap (or similar structure) tracks the current depth. Depending on the depth, nodes are appended to the left or right of the current level list. This achieves the zigzag pattern as the recursion progresses.
from typing import List, Optional
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
res = []
self.dfs(root, 0, res)
return res
def dfs(self, node, depth, res):
if not node:
return
if len(res) <= depth:
res.append([])
if depth % 2 == 0:
res[depth].append(node.val)
else:
res[depth].insert(0, node.val)
self.dfs(node.left, depth + 1, res)
self.dfs(node.right, depth + 1, res)import java.util.*;
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
public class Solution {
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
List<List<Integer>> results = new ArrayList<>();
dfs(root, 0, results);
return results;
}
private void dfs(TreeNode node, int depth, List<List<Integer>> results) {
if (node == null) return;
if (depth >= results.size()) {
results.add(new LinkedList<Integer>());
}
if (depth % 2 == 0) {
results.get(depth).add(node.val);
} else {
results.get(depth).add(0, node.val);
}
dfs(node.left, depth + 1, results);
dfs(node.right, depth + 1, results);
}
}#include <iostream>
#include <vector>
using namespace std;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:
vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
vector<vector<int>> res;
dfs(root, 0, res);
return res;
}
private:
void dfs(TreeNode* node, int depth, vector<vector<int>>& res) {
if (node == NULL) return;
if (depth >= res.size()) {
res.push_back(vector<int>());
}
if (depth % 2 == 0) {
res[depth].push_back(node->val);
} else {
res[depth].insert(res[depth].begin(), node->val);
}
dfs(node->left, depth + 1, res);
dfs(node->right, depth + 1, res);
}
};var zigzagLevelOrder = function(root) {
const result = [];
dfs(root, 0, result);
return result;
};
function dfs(node, depth, result) {
if (!node) return;
if (result.length === depth) {
result.push([]);
}
if (depth % 2 === 0) {
result[depth].push(node.val);
} else {
result[depth].unshift(node.val);
}
dfs(node.left, depth + 1, result);
dfs(node.right, depth + 1, result);
}#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
// Definition for a binary tree node.
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
};
void dfs(struct TreeNode* node, int depth, int **result, int *columnSizes, int *returnSize) {
if (!node) return;
if (depth == *returnSize) {
result[*returnSize] = (int*) malloc(2000 * sizeof(int)); // Assuming max size
columnSizes[*returnSize] = 0;
(*returnSize)++;
}
if (depth % 2 == 0) {
result[depth][columnSizes[depth]++] = node->val;
} else {
for (int i = columnSizes[depth]; i > 0; --i) {
result[depth][i] = result[depth][i - 1];
}
result[depth][0] = node->val;
columnSizes[depth]++;
}
dfs(node->left, depth + 1, result, columnSizes, returnSize);
dfs(node->right, depth + 1, result, columnSizes, returnSize);
}
int** zigzagLevelOrder(struct TreeNode* root, int** columnSizes, int* returnSize) {
int **result = (int**) malloc(2000 * sizeof(int*));
*columnSizes = (int*) malloc(2000 * sizeof(int));
*returnSize = 0;
dfs(root, 0, result, *columnSizes, returnSize);
return result;
}using System;
using System.Collections.Generic;
public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int x) { val = x; }
}
public class Solution {
public IList<IList<int>> ZigzagLevelOrder(TreeNode root) {
IList<IList<int>> results = new List<IList<int>>();
dfs(root, 0, results);
return results;
}
private void dfs(TreeNode node, int depth, IList<IList<int>> results) {
if (node == null) return;
if (results.Count == depth) {
results.Add(new List<int>());
}
if (depth % 2 == 0) {
results[depth].Add(node.val);
} else {
results[depth].Insert(0, node.val);
}
dfs(node.left, depth + 1, results);
dfs(node.right, depth + 1, results);
}
}In Python, DFS is employed to traverse the tree, inserting node values into lists representing their respective depths. Reversal on odd levels is achieved through index manipulations using Python's dynamic list capabilities.
Time Complexity: O(n), as each node is visited once during DFS.
Space Complexity: O(n), due to depth lists and recursion stack consumption.
Approach 3: BFS
To implement zigzag level order traversal, we need to add a flag left on the basis of level order traversal. This flag is used to mark the order of the node values in the current level. If left is true, the node values of the current level are stored in the result array ans from left to right. If left is false, the node values of the current level are stored in the result array ans from right to left.
The time complexity is O(n), and the space complexity is O(n). Here, n is the number of nodes in the binary tree.
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function zigzagLevelOrder(root: TreeNode | null): number[][] {
const ans: number[][] = [];
if (!root) {
return ans;
}
const q: TreeNode[] = [root];
let left: number = 1;
while (q.length) {
const t: number[] = [];
const qq: TreeNode[] = [];
for (const { val, left, right } of q) {
t.push(val);
left && qq.push(left);
right && qq.push(right);
}
ans.push(left ? t : t.reverse());
q.splice(0, q.length, ...qq);
left ^= 1;
}
return ans;
}/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func zigzagLevelOrder(root *TreeNode) (ans [][]int) {
if root == nil {
return
}
q := []*TreeNode{root}
left := true
for len(q) > 0 {
t := []int{}
for n := len(q); n > 0; n-- {
node := q[0]
q = q[1:]
t = append(t, node.Val)
if node.Left != nil {
q = append(q, node.Left)
}
if node.Right != nil {
q = append(q, node.Right)
}
}
if !left {
for i, j := 0, len(t)-1; i < j; i, j = i+1, j-1 {
t[i], t[j] = t[j], t[i]
}
}
ans = append(ans, t)
left = !left
}
return
}// Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
// pub val: i32,
// pub left: Option<Rc<RefCell<TreeNode>>>,
// pub right: Option<Rc<RefCell<TreeNode>>>,
// }
//
// impl TreeNode {
// #[inline]
// pub fn new(val: i32) -> Self {
// TreeNode {
// val,
// left: None,
// right: None
// }
// }
// }
use std::cell::RefCell;
use std::collections::VecDeque;
use std::rc::Rc;
impl Solution {
pub fn zigzag_level_order(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<Vec<i32>> {
let mut ans = Vec::new();
let mut left = true;
if let Some(root_node) = root {
let mut q = VecDeque::new();
q.push_back(root_node);
while !q.is_empty() {
let mut t = Vec::new();
for _ in 0..q.len() {
if let Some(node) = q.pop_front() {
let node_ref = node.borrow();
t.push(node_ref.val);
if let Some(ref left) = node_ref.left {
q.push_back(Rc::clone(left));
}
if let Some(ref right) = node_ref.right {
q.push_back(Rc::clone(right));
}
}
}
if !left {
t.reverse();
}
ans.push(t);
left = !left;
}
}
ans
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Breadth-First Search with Direction Toggle | Time Complexity: O(n), where n represents the number of nodes. |
| Depth-First Search with Depth Registration | Time Complexity: O(n), as each node is visited once during DFS. |
| BFS | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Breadth-First Search with Direction Toggle | O(n) | O(n) | Best general solution for level-order traversal problems and the most common interview answer |
| Depth-First Search with Depth Registration | O(n) | O(n) | Useful when you prefer recursion or want to build levels during DFS traversal |
Frequently asked questions
Is Binary Tree Zigzag Level Order Traversal easy or hard?
This problem is generally classified as Medium difficulty. The core logic is standard BFS traversal, but the zigzag ordering adds a small twist that requires careful handling of level direction or insertion order.
How to solve Binary Tree Zigzag Level Order Traversal in O(n)?
Use level-order traversal with a queue. For each level, iterate through all nodes currently in the queue, collect their values, and enqueue their children. Alternate the insertion order or reverse the level array based on a direction flag. Since each node is processed once, the algorithm runs in O(n).
Binary Tree Zigzag Level Order Traversal Python or Java solution?
In Python, developers typically use collections.deque for efficient queue operations and append or reverse lists for zigzag order. In Java, a Queue<TreeNode> with LinkedList is commonly used, while ArrayList stores the level results with direction-based insertion.
What is the best approach for Binary Tree Zigzag Level Order Traversal?
The most common approach uses Breadth-First Search (BFS) with a direction toggle. Process the tree level by level using a queue and alternate the order of values for each level. This method visits every node once and runs in O(n) time with O(n) space.
What data structure is used in Binary Tree Zigzag Level Order Traversal?
The primary data structure is a queue for Breadth-First Search to process nodes level by level. The solution also uses arrays or lists to store values at each level and a boolean flag or deque behavior to alternate traversal direction.
What is the time complexity of Binary Tree Zigzag Level Order Traversal?
Both BFS and DFS solutions run in O(n) time because each node in the binary tree is visited exactly once. Space complexity is O(n) due to storing the result levels and maintaining either a queue (BFS) or recursion stack plus result list (DFS).
Is Binary Tree Zigzag Level Order Traversal asked at Google, Amazon, or Meta?
Binary tree traversal problems are very common at companies like Google, Amazon, and Meta. Zigzag level order traversal specifically tests understanding of BFS, queue usage, and level-based processing, which frequently appear in technical interviews.