Zigzag Level Traversal of a Tree

medium tree bfs

Problem

Return the values of the tree level-by-level, but flip the order on alternate levels: level 0 left-to-right, level 1 right-to-left, level 2 left-to-right, and so on.

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(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 zigzag(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>> zigzag(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>> zigzag(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;
}

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