Binary Tree Zigzag Level Order Traversal

Medium
1906.

Binary Tree Zigzag Level Order Traversal

Binary Tree Zigzag Level Order Traversal is a medium coding problem on breadth-first search and trees, asked in Amazon, Microsoft, Meta and Bloomberg interviews.

Given the root of a binary tree, return its node values level by level in zigzag order: the root's level is read from left to right, the next level from right to left, the one after from left to right again, and so on, alternating at every level.

Example 1

Input
root = [3,9,20,null,null,15,7]
Output
[[3],[20,9],[15,7]]
Explanation
Level 1 reads left to right, level 2 right to left (20 before 9), level 3 left to right again.

Example 2

Input
root = [1,2,3,4,null,null,5]
Output
[[1],[3,2],[4,5]]
Explanation
Level 2 is read right to left: 3, 2. Level 3 is read left to right: 4, 5.

Example 3

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

Constraints

  • 0 <= number of nodes <= 2000
  • -100 <= Node.val <= 100
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * Definition for a binary tree node (provided by the judge — do not redefine it):
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var zigzagLevelOrder = function(root) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Binary Tree Zigzag Level Order Traversal — Solution

Binary Tree Zigzag Level Order Traversal solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Binary Tree Zigzag Level Order Traversal is a medium coding problem on breadth-first search and trees, asked in Amazon, Microsoft, Meta and Bloomberg interviews.

Problem statement

Given the root of a binary tree, return its node values level by level in zigzag order: the root's level is read from left to right, the next level from right to left, the one after from left to right again, and so on, alternating at every level.

Example 1

Input: root = [3,9,20,null,null,15,7]
Output: [[3],[20,9],[15,7]]
Explanation: Level 1 reads left to right, level 2 right to left (20 before 9), level 3 left to right again.

Example 2

Input: root = [1,2,3,4,null,null,5]
Output: [[1],[3,2],[4,5]]
Explanation: Level 2 is read right to left: 3, 2. Level 3 is read left to right: 4, 5.

Example 3

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

Constraints

  • 0 <= number of nodes <= 2000
  • -100 <= Node.val <= 100

Hints for Binary Tree Zigzag Level Order Traversal

  1. Hint 1

    Start from an ordinary level-order traversal: one list per level, left to right.

  2. Hint 2

    The zigzag only changes the order inside each level, never which nodes are on it.

  3. Hint 3

    Keep a flag that flips after every level, and fill each level's list from the front or from the back according to it — the queue itself always runs left to right.

How to solve Binary Tree Zigzag Level Order Traversal

Run a normal breadth-first level traversal and reverse the direction in which every other level's values are written.

Approach

  1. If the tree is empty, return an empty list.
  2. Process the tree level by level with a queue, children added left before right.
  3. For a level of size nodes, create a list of that size; the i-th node taken goes to index i on a left-to-right level and to index size - 1 - i on a right-to-left one.
  4. Append the list and flip the direction before the next level.

Why it works

The traversal itself never changes, so every level contains exactly its nodes; writing them into mirrored positions on alternate levels produces precisely the right-to-left reading of those levels.

Complexity

  • Time — O(n)
  • Space — O(w), w the largest number of nodes on one level (plus the output)

Pitfalls

  • Do not try to reverse the order children are enqueued — that scrambles the next level instead of reversing this one.
  • The first level (the root) is read left to right.

Reference solution

Python

from typing import List, Optional

def zigzagLevelOrder(root: Optional[TreeNode]) -> List[List[int]]:
    out = []
    level = [root] if root else []
    left_to_right = True
    while level:
        row = [node.val for node in level]
        if not left_to_right:
            row.reverse()
        out.append(row)
        left_to_right = not left_to_right
        nxt = []
        for node in level:
            if node.left:
                nxt.append(node.left)
            if node.right:
                nxt.append(node.right)
        level = nxt
    return out

Java

public static int[][] zigzagLevelOrder(TreeNode root) {
    List<int[]> out = new ArrayList<>();
    Deque<TreeNode> queue = new ArrayDeque<>();
    if (root != null) queue.add(root);
    boolean leftToRight = true;
    while (!queue.isEmpty()) {
        int size = queue.size();
        int[] row = new int[size];
        for (int i = 0; i < size; i++) {
            TreeNode node = queue.poll();
            row[leftToRight ? i : size - 1 - i] = node.val;
            if (node.left != null) queue.add(node.left);
            if (node.right != null) queue.add(node.right);
        }
        out.add(row);
        leftToRight = !leftToRight;
    }
    return out.toArray(new int[0][]);
}

C++

vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
    vector<vector<int>> out;
    queue<TreeNode*> q;
    if (root) q.push(root);
    bool leftToRight = true;
    while (!q.empty()) {
        int size = (int) q.size();
        vector<int> row(size);
        for (int i = 0; i < size; i++) {
            TreeNode* node = q.front();
            q.pop();
            row[leftToRight ? i : size - 1 - i] = node->val;
            if (node->left) q.push(node->left);
            if (node->right) q.push(node->right);
        }
        out.push_back(row);
        leftToRight = !leftToRight;
    }
    return out;
}

JavaScript

var zigzagLevelOrder = function(root) {
    var out = [];
    if (root === null) return out;
    var queue = [root], head = 0, leftToRight = true;
    while (head < queue.length) {
        var end = queue.length, size = end - head, row = new Array(size);
        for (var i = 0; i < size; i++) {
            var node = queue[head++];
            row[leftToRight ? i : size - 1 - i] = node.val;
            if (node.left !== null) queue.push(node.left);
            if (node.right !== null) queue.push(node.right);
        }
        out.push(row);
        leftToRight = !leftToRight;
    }
    return out;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 156 breadth-first search problems · the whole catalogue

Learn the technique: Breadth-First Search (BFS) · Binary Trees and Tree Traversals