Binary Tree Zigzag Level Order Traversal

Given a binary tree, return its values level by level. The first level is read left to right, the next right to left, and so on, alternating.

LeetCode: 103. Binary Tree Zigzag Level Order Traversal

Example

Text

      3
     / \
    9   20          Output: [[3], [20, 9], [15, 7]]
       /  \
      15   7

      1
     / \
    2   3           Output: [[1], [3, 2], [4, 5, 6, 7]]
   / \ / \
  4  5 6  7

Level order, reversing every other level

Run a normal breadth-first traversal one level at a time, and reverse the odd-numbered levels before saving them. ArrayDeque is Java's array-backed double-ended queue: add appends at the back and poll removes from the front. A tree node is an object with left and right references, and an empty subtree is null.

Java

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Queue;

public class Main {
    static class TreeNode {
        int val;
        TreeNode left, right;

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    static TreeNode leaf(int val) {
        return new TreeNode(val, null, null);
    }

    static List<List<Integer>> zigzag(TreeNode root) {
        List<List<Integer>> levels = new ArrayList<>();
        if (root == null) return levels;
        Queue<TreeNode> queue = new ArrayDeque<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            List<Integer> level = new ArrayList<>(size);
            for (int i = 0; i < size; i++) {
                TreeNode n = queue.poll();
                level.add(n.val);
                if (n.left != null) queue.add(n.left);
                if (n.right != null) queue.add(n.right);
            }
            if (levels.size() % 2 == 1) {
                Collections.reverse(level);
            }
            levels.add(level);
        }
        return levels;
    }

    public static void main(String[] args) {
        System.out.println(zigzag(new TreeNode(3, leaf(9), new TreeNode(20, leaf(15), leaf(7)))));
        System.out.println(zigzag(new TreeNode(1,
            new TreeNode(2, leaf(4), leaf(5)),
            new TreeNode(3, leaf(6), leaf(7)))));
    }
}

Output

[[3], [20, 9], [15, 7]]
[[1], [3, 2], [4, 5, 6, 7]]

Time: O(n): every node is visited once, and the reversals touch each value once more. Space: O(w) for the widest level.

Two stacks

A stack reverses the order of whatever is pushed onto it. Pop the current level from one stack, and push the children onto the other. ArrayDeque also serves as the stack: push and pop work on the front, so the last value pushed is the first popped.

On a left-to-right level, push each node's left child, then its right child. The next level pops right to left.
On a right-to-left level, push the right child first, then the left. The next level pops left to right.

The zigzag order comes out directly, with no reversing.

Java

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

public class Main {
    static class TreeNode {
        int val;
        TreeNode left, right;

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    static TreeNode leaf(int val) {
        return new TreeNode(val, null, null);
    }

    static List<List<Integer>> zigzag(TreeNode root) {
        List<List<Integer>> levels = new ArrayList<>();
        if (root == null) return levels;
        Deque<TreeNode> current = new ArrayDeque<>();
        current.push(root);
        boolean leftToRight = true;
        while (!current.isEmpty()) {
            Deque<TreeNode> next = new ArrayDeque<>();
            List<Integer> level = new ArrayList<>(current.size());
            while (!current.isEmpty()) {
                TreeNode n = current.pop();
                level.add(n.val);
                TreeNode first = leftToRight ? n.left : n.right;
                TreeNode second = leftToRight ? n.right : n.left;
                if (first != null) next.push(first);
                if (second != null) next.push(second);
            }
            levels.add(level);
            current = next;
            leftToRight = !leftToRight;
        }
        return levels;
    }

    public static void main(String[] args) {
        System.out.println(zigzag(new TreeNode(3, leaf(9), new TreeNode(20, leaf(15), leaf(7)))));
        System.out.println(zigzag(new TreeNode(1,
            new TreeNode(2, leaf(4), leaf(5)),
            new TreeNode(3, leaf(6), leaf(7)))));
        System.out.println(zigzag(null));
    }
}

Output

[[3], [20, 9], [15, 7]]
[[1], [3, 2], [4, 5, 6, 7]]
[]

Time: O(n). Space: O(w).

Both approaches have the same complexity. The two-stack version saves the reversal work and shows why the order alternates; the BFS version is easier to get right in an interview.

Edge cases

Empty tree: an empty list.
Skewed tree: one node per level, so the direction doesn't matter.