Binary Tree Zigzag Level Order Traversal

Ishaan S Published 24 Oct, 2026

You are given the root of a binary tree. Group its values by depth and return one list per level, from the root level down to the deepest level.

The reading direction alternates from level to level: read the root level left to right, the next level right to left, the one after that left to right again, and so on. If the tree is empty, return an empty list.

The tree is given as a level-order array in which null marks a missing child, so [1,2,3,null,4] is a root 1 with children 2 and 3, where 2 has only a right child 4.

Example 1

Input: root = [8,3,10,1,6,null,14,null,null,4,7] Output: [[8],[10,3],[1,6,14],[7,4]] Why: Level 0 is [8]. Level 1 is read right to left: [10, 3]. Level 2 left to right: [1, 6, 14]. Level 3 right to left: [7, 4].

Example 2

Input: root = [] Output: [] Why: An empty tree has no levels.

Example 3

Input: root = [42] Output: [[42]] Why: A single node gives a single level.

Constraints

The number of nodes is between 0 and 2000.
-100 <= Node.val <= 100

Pattern Path · Trees: BFS · problem 95 of 169

Ignore the alternating direction for a moment. How would you collect the values of each level, left to right?

A queue-based breadth-first search handles one level per round if you note how many nodes the queue holds when the round starts.

Keep the traversal itself unchanged and only decide how to record each level: on odd levels, reverse the list (or fill it from the back) before adding it to the answer.

Target: O(n) time, O(n) extra space.

Start simple

Run a separate depth-first search for every depth d to collect that level's nodes: O(n·h) time, which is O(n²) for a skewed tree.

The key idea

This is an ordinary level-order traversal with a twist that only affects how each level is written down, not how the tree is visited.

Use a queue. At the start of each round the queue holds exactly the nodes of one level, so record its size k, pop k nodes, collect their values in left-to-right order, and push their children (left first, then right) for the next round.

Keep a flag that flips after every level. When the flag says "right to left", reverse the collected values before appending them. Reversing a level of size k costs O(k), and every node belongs to exactly one level, so the total extra work is O(n).

Do not try to change the order in which children are pushed: that changes which nodes are visited next and quickly scrambles deeper levels. Keeping the visit order fixed and only reversing the output is what keeps the logic simple and correct.

Complexity

Time: O(n)
Space: O(n)

Python

from collections import deque

class Solution:
    def zigzagLevelOrder(self, root):
        if root is None:
            return []
        result = []
        queue = deque([root])
        left_to_right = True
        while queue:
            level = []
            for _ in range(len(queue)):        # exactly the nodes of this level
                node = queue.popleft()
                level.append(node.val)
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            if not left_to_right:
                level.reverse()
            result.append(level)
            left_to_right = not left_to_right
        return result

JavaScript

var zigzagLevelOrder = function(root) {
  if (root === null) return [];
  const result = [];
  let level = [root];
  let leftToRight = true;
  while (level.length > 0) {
    const values = level.map(node => node.val);
    if (!leftToRight) values.reverse();
    result.push(values);
    const next = [];
    for (const node of level) {
      if (node.left) next.push(node.left);
      if (node.right) next.push(node.right);
    }
    level = next;
    leftToRight = !leftToRight;
  }
  return result;
};

What the interviewer is checking

It checks that you can run a level-by-level BFS cleanly and adapt it to a small twist without breaking the traversal itself.

Mistakes to avoid

Swapping the order children are enqueued on alternate levels, which corrupts the order of later levels.
Forgetting to handle an empty tree (root is null).
Not fixing the level size before the inner loop, so nodes from the next level get mixed into the current one.
Starting with the wrong direction: the root level is read left to right.

Follow-ups to expect

Can you avoid the reversal? (Fill each level from the front or back.)
Can you do it with depth-first search? (Pass depth, append to level list.)
Can you use two stacks instead of a queue? (Alternate stacks, alternate child order.)

In real software

Level-by-level traversal shows up in rendering org charts and file trees by depth, and in breadth-first crawlers that process one hop distance at a time.

Practice next

import java.util.*;

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) { this.val = val; }
}

class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        return new ArrayList<>();
    }
}

public class Main {
    // Builds a tree from a level-order array (null = missing child).
    static TreeNode build(Integer[] a) {
        if (a.length == 0 || a[0] == null) return null;
        TreeNode root = new TreeNode(a[0]);
        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);
        int i = 1;
        while (i < a.length) {
            TreeNode node = q.poll();
            if (i < a.length && a[i] != null) { node.left = new TreeNode(a[i]); q.add(node.left); }
            i++;
            if (i < a.length && a[i] != null) { node.right = new TreeNode(a[i]); q.add(node.right); }
            i++;
        }
        return root;
    }

public static void main(String[] args) {
        TreeNode root = build(new Integer[]{8, 3, 10, 1, 6, null, 14, null, null, 4, 7});
        System.out.println(new Solution().zigzagLevelOrder(root)); // [[8], [10, 3], [1, 6, 14], [7, 4]]
    }
}

#include <bits/stdc++.h>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

const int NIL = INT_MIN;  // marks a missing child in the level-order array

// Builds a tree from a level-order array.
TreeNode* build(const vector<int>& a) {
    if (a.empty() || a[0] == NIL) return nullptr;
    TreeNode* root = new TreeNode(a[0]);
    queue<TreeNode*> q;
    q.push(root);
    size_t i = 1;
    while (i < a.size()) {
        TreeNode* node = q.front(); q.pop();
        if (i < a.size() && a[i] != NIL) { node->left = new TreeNode(a[i]); q.push(node->left); }
        i++;
        if (i < a.size() && a[i] != NIL) { node->right = new TreeNode(a[i]); q.push(node->right); }
        i++;
    }
    return root;
}

class Solution {
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        return {};
    }
};

int main() {
    TreeNode* root = build({8, 3, 10, 1, 6, NIL, 14, NIL, NIL, 4, 7});
    for (auto& level : Solution().zigzagLevelOrder(root)) {
        for (int x : level) cout << x << ' ';
        cout << '\n';
    }
    // 8 / 10 3 / 1 6 14 / 7 4 (one level per line)
}

Topics #095 #t-tree-bfs BFS Medium Practice Queue Tree