Zig-Zag traversal of a binary tree

The problem, simply

You get a binary tree. Read it one row (level) at a time, but change direction on every row: the top row left to right, the next row right to left, the next left to right again, and so on. Give back each row as its own list.

A story to remember it

Picture it

Examples

Way 1: the simple way

Do a normal row by row reading with a waiting line (a queue). Every second row, turn the row's list around before you save it.

1. Put the root in the line. Set leftToRight = true.
2. Read the line's size and take that many nodes, writing their values into a row list and adding their children to the back.
3. If leftToRight is false, reverse the row list.
4. Save the row, flip leftToRight, and repeat.

import java.util.*;

class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> out = new ArrayList<>();
        if (root == null) return out;
        Queue<TreeNode> line = new ArrayDeque<>();
        line.add(root);
        boolean leftToRight = true;
        while (!line.isEmpty()) {
            int size = line.size();
            List<Integer> row = new ArrayList<>();
            for (int i = 0; i < size; i++) {
                TreeNode node = line.poll();
                row.add(node.val);
                if (node.left != null) line.add(node.left);
                if (node.right != null) line.add(node.right);
            }
            if (!leftToRight) Collections.reverse(row);   // turn the row around
            out.add(row);
            leftToRight = !leftToRight;
        }
        return out;
    }
}

How long it takes: each node once, plus turning some rows around, which also touches each node at most once, O(n). Extra room: one row in the line, O(w) where w is the widest row.

Way 2: the clever way

Use two piles (stacks): now holds the row you are reading, next collects the row below. You always pop from the top of now.

1. Push the root on now. Set leftToRight = true.
2. Pop a node from now and write it in the row.
3. If leftToRight, push its left child then its right child on next. Otherwise push right then left.
4. When now is empty, the row is finished. Save it, swap the piles, and flip the direction.

Why it works: the pile turns things around. Children pushed left then right come out right then left, which is exactly the next row's direction.

import java.util.*;

class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> out = new ArrayList<>();
        if (root == null) return out;
        Deque<TreeNode> now = new ArrayDeque<>();
        Deque<TreeNode> next = new ArrayDeque<>();
        now.push(root);
        boolean leftToRight = true;
        List<Integer> row = new ArrayList<>();
        while (!now.isEmpty()) {
            TreeNode node = now.pop();
            row.add(node.val);
            if (leftToRight) {                       // next row comes out right to left
                if (node.left != null) next.push(node.left);
                if (node.right != null) next.push(node.right);
            } else {                                 // next row comes out left to right
                if (node.right != null) next.push(node.right);
                if (node.left != null) next.push(node.left);
            }
            if (now.isEmpty()) {                     // this row is finished
                out.add(row);
                row = new ArrayList<>();
                Deque<TreeNode> swap = now;
                now = next;
                next = swap;
                leftToRight = !leftToRight;
            }
        }
        return out;
    }
}

How long it takes: every node is pushed and popped once, O(n), and nothing is ever reversed. Extra room: the two piles together hold at most two rows, O(w).

Watch out for

• Do not reverse the waiting line itself in Way 1. Only reverse the row list you save; the line must stay in normal left to right order.
• Using one stack instead of two mixes the current row with the next one.
• An empty tree returns an empty list.

What interviewers ask next

• Can you avoid the reverse in the queue version? Yes. Fill each row with a deque: add to the back on left to right rows and to the front on right to left rows.
• Print the whole zigzag as one flat list instead of rows. Same code, but add every value to one list.
• Spiral order of a matrix is a different problem; do not mix them up, but the "turn around every pass" feeling is the same.
• Which is better? All three are O(n). The deque row version is the shortest to write in an interview; the two stack version shows you understand why stacks reverse.

Remember this

Grown-up words: rows are levels, the waiting line is a queue for breadth first search, the piles are stacks (last in, first out), and a line that you can use from both ends is a deque.