Binary Tree Zigzag Level Order Traversal medium

Problem Statement

Given the root of a binary tree, return the zigzag level order traversal of its nodes' values. (i.e., from left to right, then right to left for the next level and alternate between).

Example 1

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

Example 2

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

Steps

1. Initialization: Create an empty list result to store the zigzag traversal. Create a queue queue to perform a Breadth-First Search (BFS) of the tree. Add the root node to the queue.

2. Iteration: While the queue is not empty, perform the following steps:

   • Get the current level size. This tells us how many nodes are at the current level.
   • Create an empty list level to store the nodes at the current level.
   • Iterate levelSize times:
     • Dequeue a node from the queue.
     • Add the node's value to the level list.
     • Enqueue the node's left and right children (if they exist).
   • Add the level list to the result list. Reverse the level list if the current level is even (0-indexed).

3. Return: Return the result list.

Explanation

The algorithm uses a Breadth-First Search (BFS) to traverse the tree level by level. The key is to reverse the order of nodes at even levels to achieve the zigzag effect. We use a queue for the BFS and keep track of the current level using the levelSize variable. The modulo operator (%) helps us determine whether the current level is even or odd.

Code

import java.util.*;

public class ZigzagTraversal {
    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; // Flag to alternate direction

        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            List<Integer> level = new ArrayList<>();

            for (int i = 0; i < levelSize; i++) {
                TreeNode node = queue.poll();
                if (leftToRight) {
                    level.add(node.val);
                } else {
                    level.add(0, node.val); // Add to beginning for right-to-left
                }

                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }

            result.add(level);
            leftToRight = !leftToRight; // Toggle direction for the next level
        }

        return result;
    }

    // Definition for a binary tree node.
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
}

Complexity

• Time Complexity: O(N), where N is the number of nodes in the tree. We visit each node once.
• Space Complexity: O(W), where W is the maximum width of the tree. In the worst case (a complete binary tree), W can be equal to N/2, but it's generally less than N. The space is primarily used by the queue.