Binary Tree Zigzag Level Order Traversal

mediumTrees: Traversal60 stepsJava · Python · C++

Like level order, but alternate direction each level: left-to-right, then right-to-left. Do a normal BFS and, on odd levels, insert values at the front of the level's list instead of the back.

▶ Watch the animated trace

Traced input: root = [3, 9, 20, null, null, 15, 7] → [[3], [20, 9], [15, 7]]. Original problem: neetcode.io/problems/binary-tree-zigzag-level-order-traversal

Complexity

BestO(n)

AverageO(n)

WorstO(n)

SpaceO(w)

Adding to the front of a LinkedList is O(1).

Key idea

The traversal order never changes; only where values go in the level list.
Flip a boolean after each level.
LinkedList.addFirst reverses a level without a separate reverse step.

Common mistakes

Changing the order children are queued breaks later levels.
Reversing with Collections.reverse is fine but an extra pass.

Solution

Java

List<List<Integer>> zigzagLevelOrder(TreeNode root) {
    List<List<Integer>> res = new ArrayList<>();
    if (root == null) return res;
    Queue<TreeNode> queue = new ArrayDeque<>();
    queue.offer(root);
    boolean leftToRight = true;
    while (!queue.isEmpty()) {
        int size = queue.size();
        LinkedList<Integer> level = new LinkedList<>();
        for (int i = 0; i < size; i++) {
            TreeNode node = queue.poll();
            if (leftToRight) level.addLast(node.val);
            else level.addFirst(node.val);
            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }
        res.add(level);
        leftToRight = !leftToRight;
    }
    return res;
}

Python

def zigzagLevelOrder(root: Optional[TreeNode]) -> List[List[int]]:
    res = []
    if not root: return res
    queue = deque([root])
    left_to_right = True
    while queue:
        level = deque()
        for _ in range(len(queue)):
            node = queue.popleft()
            if left_to_right: level.append(node.val)
            else: level.appendleft(node.val)
            if node.left: queue.append(node.left)
            if node.right: queue.append(node.right)
        res.append(list(level))
        left_to_right = not left_to_right
    return res

C++

vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
    vector<vector<int>> res;
    if (!root) return res;
    queue<TreeNode*> q;
    q.push(root);
    bool leftToRight = true;
    while (!q.empty()) {
        deque<int> level;
        for (int i = q.size(); i > 0; i--) {
            TreeNode* node = q.front(); q.pop();
            if (leftToRight) level.push_back(node->val);
            else level.push_front(node->val);
            if (node->left) q.push(node->left);
            if (node->right) q.push(node->right);
        }
        res.emplace_back(level.begin(), level.end());
        leftToRight = !leftToRight;
    }
    return res;
}

Edge cases

Each one has its own trace in the interactive view.

Case	Input	Answer
Empty tree No levels.	`root = []`	`[]`
Three full levels The third level reads left to right again.	`root = [1, 2, 3, 4, 5, 6, 7]`	`[[1], [3, 2], [4, 5, 6, 7]]`
Single node One level.	`root = [1]`	`[[1]]`