Binary Tree Zigzag Level Order Traversal

medium tree bfs

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).

Run a normal level-order BFS that always enqueues children left-then-right; just record each level into an array, and reverse the array on every odd level before appending to the result.

Inputlevel-order: [3, 9, 20, _, _, 15, 7]

Output[[3], [20, 9], [15, 7]]

level-order ('_' for null)

from collections import deque
def zigzag_level_order(root):
    out, q, lvl = [], deque([root]) if root else deque(), 0
    while q:
        n = len(q); row = []
        for _ in range(n):
            node = q.popleft()
            row.append(node.val)
            if node.left:  q.append(node.left)
            if node.right: q.append(node.right)
        if lvl % 2 == 1: row.reverse()
        out.append(row); lvl += 1
    return out

function zigzagLevelOrder(root) {
  const out = []; const q = root ? [root] : [];
  let lvl = 0;
  while (q.length) {
    const n = q.length; const row = [];
    for (let i = 0; i < n; i++) {
      const node = q.shift();
      row.push(node.val);
      if (node.left)  q.push(node.left);
      if (node.right) q.push(node.right);
    }
    if (lvl % 2 === 1) row.reverse();
    out.push(row); lvl++;
  }
  return out;
}

class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> out = new ArrayList<>();
        if (root == null) return out;
        Deque<TreeNode> q = new ArrayDeque<>(); q.add(root);
        int lvl = 0;
        while (!q.isEmpty()) {
            int n = q.size(); List<Integer> row = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                TreeNode node = q.poll();
                row.add(node.val);
                if (node.left != null)  q.add(node.left);
                if (node.right != null) q.add(node.right);
            }
            if (lvl % 2 == 1) Collections.reverse(row);
            out.add(row); lvl++;
        }
        return out;
    }
}

vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
    vector<vector<int>> out;
    if (!root) return out;
    queue<TreeNode*> q; q.push(root);
    int lvl = 0;
    while (!q.empty()) {
        int n = q.size();
        vector<int> row;
        for (int i = 0; i < n; i++) {
            auto node = q.front(); q.pop();
            row.push_back(node->val);
            if (node->left)  q.push(node->left);
            if (node->right) q.push(node->right);
        }
        if (lvl % 2 == 1) reverse(row.begin(), row.end());
        out.push_back(row); lvl++;
    }
    return out;
}

Explanation

Zigzag order is just a normal level-order BFS with one twist: every other level is read backwards. The trick is to keep the traversal simple and only reverse the row when needed.

We process the tree one full level at a time. At the start of each level we record n = q.length, then pop exactly n nodes into a list row, always enqueuing children left then right so the next level is in normal order.

Before adding row to the output, we check the level number. On odd levels (lvl % 2 == 1) we reverse the row; on even levels we leave it as-is. A counter lvl increments each level to alternate the direction.

Example: tree [3, 9, 20, null, null, 15, 7]. Level 0 is [3] (kept). Level 1 collects [9, 20] and reverses to [20, 9]. Level 2 collects [15, 7] (kept). Result: [[3], [20, 9], [15, 7]].

Each node is enqueued and dequeued once, so the traversal is O(n) time.

Time: O(n) Space: O(w) queue width