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 array result to store the zigzag traversal levels. Initialize a queue queue with the root node. Initialize a variable level to 0 to track the current level. Initialize a boolean variable leftToRight to true to indicate the traversal direction.

2. Level Order Traversal: While the queue is not empty:

   • Get the number of nodes levelSize at the current level.
   • Create an empty array levelNodes to store the nodes at the current level.
   • Iterate levelSize times:
     • Dequeue a node from the queue.
     • If leftToRight is true, append the node's value to levelNodes.
     • Otherwise (if leftToRight is false), prepend the node's value to levelNodes.
     • Enqueue the node's left and right children (if they exist).
   • Append levelNodes to the result array.
   • Toggle leftToRight for the next level.
   • Increment level.

3. Return: Return the result array.

Explanation

The algorithm uses a level-order traversal (breadth-first search) to process the tree level by level. The leftToRight flag controls the order in which nodes are added to the levelNodes array for each level. By toggling this flag, we achieve the zigzag pattern. Using a queue ensures that we process nodes at each level before moving to the next. Prepending and appending to levelNodes efficiently handles the direction change.

Code

class TreeNode {
    val: number;
    left: TreeNode | null;
    right: TreeNode | null;
    constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
        this.val = val === undefined ? 0 : val;
        this.left = left === undefined ? null : left;
        this.right = right === undefined ? null : right;
    }
}

function zigzagLevelOrder(root: TreeNode | null): number[][] {
    if (!root) return [];

    const result: number[][] = [];
    const queue: TreeNode[] = [root];
    let level = 0;
    let leftToRight = true;

    while (queue.length > 0) {
        const levelSize = queue.length;
        const levelNodes: number[] = [];

        for (let i = 0; i < levelSize; i++) {
            const node = queue.shift()!;
            if (leftToRight) {
                levelNodes.push(node.val);
            } else {
                levelNodes.unshift(node.val);
            }
            if (node.left) queue.push(node.left);
            if (node.right) queue.push(node.right);
        }

        result.push(levelNodes);
        leftToRight = !leftToRight;
        level++;
    }

    return result;
}

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, but in general it's less than N. The space is used by the queue.