5.3 Binary Tree Zigzag Level Order Traversal

5.3.1 Problem Metadata

5.3.2 Description

Return the zigzag level order traversal of a binary tree (left-to-right, then right-to-left, alternating each level).

5.3.3 Examples

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

5.3.4 Constraints

  • 0 <= nodes <= 2000

5.3.5 Solution - BFS with Direction Flag

5.3.5.1 Walkthrough

Perform level-order traversal. Track a boolean indicating whether to append values normally or reversed. For every level, either append values or insert at the front, and flip the flag.

5.3.5.2 Analysis

  • Time Complexity: O(n)
  • Space Complexity: O(n)

5.3.5.3 Implementation Steps

  1. Initialize queue with root and a boolean leftToRight = true.
  2. For each level, collect values in a list.
  3. If leftToRight, append; otherwise insert at front or use reverse list.
  4. Toggle leftToRight each level.

5.3.5.4 Code - Java

public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
    List<List<Integer>> result = new ArrayList<>();
    if (root == null) {
        return result;
    }

    Queue<TreeNode> queue = new LinkedList<>();
    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);
            }
        }

        result.add(level);
        leftToRight = !leftToRight;
    }

    return result;
}