Binary Tree Zigzag Level Order Traversal

Medium Problem 72 of 151 Java and Python

Problem

Given the root of a binary tree, return the zigzag level order traversal of its values: the first level left to right, the next right to left, and so on, alternating.

Example 1

Input: root = [3, 9, 20, null, null, 15, 7]
Output: [[3], [20, 9], [15, 7]]

Example 2

Input: root = [1]
Output: [[1]]

Constraints

0 ≤ number of nodes ≤ 2000

Explanation

Do a normal level-order BFS; only the order you write each level changes. On right-to-left levels, fill the level array from its end.

Approach 1 · Naive

Level order, then reverse odd levels

Time O(n)
Space O(w)

Build the ordinary level-order lists, then reverse every second list.

Collect level-order lists with BFS.
Reverse the lists at odd indexes.

Java

import java.util.*;

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

Python

from collections import deque

class Solution:
    def zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        result = []
        queue = deque([root] if root else [])
        while queue:
            level = []
            for _ in range(len(queue)):
                node = queue.popleft()
                level.append(node.val)
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            result.append(level[::-1] if len(result) % 2 else level)
        return result

Approach 2 · Optimal

Write each value at its final position

Time O(n)
Space O(w)

Know the level size up front and place each value at index i or size - 1 - i depending on the direction, so no reversal is needed.

For each level of size size, create an array of that length.
For the i-th node popped, write its value at i (left-to-right) or size - 1 - i (right-to-left).
Flip the direction after each level.

Java

import java.util.*;

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

Python

from collections import deque

class Solution:
    def zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        result = []
        queue = deque([root] if root else [])
        left_to_right = True
        while queue:
            size = len(queue)
            level = [0] * size
            for i in range(size):
                node = queue.popleft()
                level[i if left_to_right else size - 1 - i] = node.val
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            result.append(level)
            left_to_right = not left_to_right
        return result

Complexity compared

Approach	Time	Space
Naive Level order, then reverse odd levels	O(n)	O(w)
Optimal Write each value at its final position	O(n)	O(w)

Key takeaways

Keep the BFS itself unchanged; changing the order children are enqueued breaks the next level.

Your notes

Saved in this browser as you type.

Solved it on your own?

Mark it done to track your progress, or star it to come back before an interview.

Next problem