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 a queue queue to perform Breadth-First Search (BFS), and a list result to store the zigzag level order traversal. Initialize queue with the root node. Also, initialize a variable leftToRight to true indicating the traversal direction for the first level.

2. BFS Traversal: While the queue is not empty:

   • Get the current level size levelSize which determines the number of nodes to process at the current level.
   • Create a list levelNodes to store nodes for the current level.
   • Iterate levelSize times:
     • Dequeue a node node from the queue.
     • Add the node's value to levelNodes.
     • Enqueue the node's left child (if it exists).
     • Enqueue the node's right child (if it exists).
   • If leftToRight is true, add levelNodes directly to result. Otherwise, reverse levelNodes before adding to result.
   • Toggle leftToRight to switch the traversal direction for the next level.

3. Return: Return the result list.

Explanation

The solution uses Breadth-First Search (BFS) to traverse the binary tree level by level. A queue is used to maintain the nodes to be processed. To achieve the zigzag traversal, a boolean variable leftToRight keeps track of the traversal direction. If leftToRight is true, nodes are added to the levelNodes list in the order they are encountered (left to right). If leftToRight is false, levelNodes is reversed before adding to the result, effectively producing a right-to-left traversal. The leftToRight variable is toggled after each level to alternate the traversal direction.

Code

using System.Collections.Generic;

public class Solution {
    public IList<IList<int>> ZigzagLevelOrder(TreeNode root) {
        IList<IList<int>> result = new List<IList<int>>();
        if (root == null) return result;

        Queue<TreeNode> queue = new Queue<TreeNode>();
        queue.Enqueue(root);
        bool leftToRight = true;

        while (queue.Count > 0) {
            int levelSize = queue.Count;
            List<int> levelNodes = new List<int>();

            for (int i = 0; i < levelSize; i++) {
                TreeNode node = queue.Dequeue();
                levelNodes.Add(node.val);
                if (node.left != null) queue.Enqueue(node.left);
                if (node.right != null) queue.Enqueue(node.right);
            }

            if (!leftToRight) {
                levelNodes.Reverse();
            }
            result.Add(levelNodes);
            leftToRight = !leftToRight;
        }

        return result;
    }
}

public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

Complexity

• Time Complexity: O(N), where N is the number of nodes in the binary tree. Each node is visited and processed exactly once.
• Space Complexity: O(W), where W is the maximum width of the binary tree. In the worst case (a complete binary tree), W can be proportional to N, resulting in O(N) space complexity. The space is primarily used by the queue to store nodes at each level.