Binary Tree Zigzag Level Order Traversal

                                            
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        vector<vector<int>> result;
        if (root == nullptr) {
            return result;
        }
        
        queue<TreeNode*> q;
        q.push(root);
        bool leftToRight = true;
        
        while (!q.empty()) {
            int size = q.size();
            vector<int> level(size);
            
            for (int i = 0; i < size; i++) {
                TreeNode* node = q.front();
                q.pop();
                
                int index = leftToRight ? i : (size - 1 - i);
                level[index] = node->val;
                
                if (node->left != nullptr) {
                    q.push(node->left);
                }
                
                if (node->right != nullptr) {
                    q.push(node->right);
                }
            }
            
            result.push_back(level);
            leftToRight = !leftToRight;
        }
        
        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;
 *     }
 * }
 */
class Solution {
    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();
            List<Integer> level = new ArrayList<>();

            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                if (leftToRight) {
                    level.add(node.val);
                } else {
                    level.add(0, 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;
    }
}

                                            
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int** zigzagLevelOrder(struct TreeNode* root, int* returnSize, int** returnColumnSizes) {
    if (!root) {
        *returnSize = 0;
        *returnColumnSizes = NULL;
        return NULL;
    }
    
    int** res = (int**)malloc(sizeof(int*) * 2000);
    *returnColumnSizes = (int*)malloc(sizeof(int) * 2000);
    *returnSize = 0;
    
    struct TreeNode** queue = (struct TreeNode**)malloc(sizeof(struct TreeNode*) * 2000);
    int front = 0, rear = 0;
    bool leftToRight = true;
    
    queue[rear++] = root;
    
    while (front < rear) {
        int levelSize = rear - front;
        int* level = (int*)malloc(sizeof(int) * levelSize);
        
        for (int i = 0; i < levelSize; i++) {
            struct TreeNode* node = queue[front++];
            int index = leftToRight ? i : levelSize - 1 - i;
            level[index] = node->val;
            
            if (node->left) queue[rear++] = node->left;
            if (node->right) queue[rear++] = node->right;
        }
        
        res[*returnSize] = level;
        (*returnColumnSizes)[*returnSize] = levelSize;
        (*returnSize)++;
        leftToRight = !leftToRight;
    }
    
    return res;
}

                                            
/**
 * Definition for a binary tree node.
 * 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;
 *     }
 * }
 */
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 zigzag = false;
        
        while (queue.Count > 0) {
            int size = queue.Count;
            IList<int> level = new List<int>();
            
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.Dequeue();
                if (zigzag) {
                    level.Insert(0, node.val);
                }
                else {
                    level.Add(node.val);
                }
                
                if (node.left != null) queue.Enqueue(node.left);
                if (node.right != null) queue.Enqueue(node.right);
            }
            
            result.Add(level);
            zigzag = !zigzag;
        }
        
        return result;
    }
}

                                            
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 */

/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var zigzagLevelOrder = function(root) {
    if (!root) return [];
    
    const result = [];
    let level = 0;
    
    const traverse = (node, level) => {
        if (!node) return;

        if (!result[level]) {
            result[level] = [];
        }
        
        if (level % 2 === 0) {
            result[level].push(node.val);  
        } else {
            result[level].unshift(node.val);  
        }
        
        traverse(node.left, level + 1);
        traverse(node.right, level + 1);
    }
    
    traverse(root, 0);
    
    return result;
};

                                            
/**
 * Definition for a binary tree node.
 * 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[][] = [];
    let level: number[] = [];
    let queue: TreeNode[] = [root];
    let zigzag: boolean = false;
    
    while (queue.length) {
        const len = queue.length;
        
        for (let i = 0; i < len; i++) {
            const node = queue.shift()!;
            if (zigzag) {
                level.unshift(node.val);
            } else {
                level.push(node.val);
            }
            
            if (node.left) queue.push(node.left);
            if (node.right) queue.push(node.right);
        }
        
        result.push(level);
        level = [];
        zigzag = !zigzag;
    }
    
    return result;
}

                                            
/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     public $val = null;
 *     public $left = null;
 *     public $right = null;
 *     function __construct($value) { $this->val = $value; }
 * }
 */

class Solution {

    /**
     * @param TreeNode $root
     * @return Integer[][]
     */
    function zigzagLevelOrder($root) {
        $result = [];
        if ($root === null) {
            return $result;
        }
        
        $queue = [];
        array_push($queue, $root);
        $zigZag = false;
        
        while (!empty($queue)) {
            $level = [];
            $count = count($queue);
            for ($i = 0; $i < $count; $i++) {
                $node = array_shift($queue);
                if ($zigZag) {
                    array_unshift($level, $node->val);
                } else {
                    array_push($level, $node->val);
                }
                
                if ($node->left !== null) {
                    array_push($queue, $node->left);
                }
                if ($node->right !== null) {
                    array_push($queue, $node->right);
                }
            }
            array_push($result, $level);
            $zigZag = !$zigZag;
        }
        
        return $result;
    }
}

                                            
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public var val: Int
 *     public var left: TreeNode?
 *     public var right: TreeNode?
 *     public init() { self.val = 0; self.left = nil; self.right = nil; }
 *     public init(_ val: Int) { self.val = val; self.left = nil; self.right = nil; }
 *     public init(_ val: Int, _ left: TreeNode?, _ right: TreeNode?) {
 *         self.val = val
 *         self.left = left
 *         self.right = right
 *     }
 * }
 */
class Solution {
    func zigzagLevelOrder(_ root: TreeNode?) -> [[Int]] {
        guard let root = root else { return [] }
        
        var result = [[Int]]()
        var queue = [root]
        var isZigZag = false
        
        while !queue.isEmpty {
            var level = [Int]()
            let size = queue.count
            
            for _ in 0..<size {
                let node = queue.removeFirst()
                
                if isZigZag {
                    level.insert(node.val, at: 0)
                } else {
                    level.append(node.val)
                }
                
                if let left = node.left {
                    queue.append(left)
                }
                if let right = node.right {
                    queue.append(right)
                }
            }
            
            result.append(level)
            isZigZag.toggle()
        }
        
        return result
    }
}

                                            
/**
 * Definition for a binary tree node.
 * class TreeNode(var `val`: Int) {
 *     var left: TreeNode? = null
 *     var right: TreeNode? = null
 * }
 */
class Solution {
    fun zigzagLevelOrder(root: TreeNode?): List<List<Int>> {
        if (root == null) return emptyList()
        
        val result = mutableListOf<List<Int>>()
        var level = 0
        val queue = LinkedList<TreeNode>()
        queue.offer(root)
        
        while (queue.isNotEmpty()) {
            val levelSize = queue.size
            val levelValues = mutableListOf<Int>()
            
            for (i in 0 until levelSize) {
                val node = queue.poll()
                
                if (level % 2 == 0) {
                    levelValues.add(node.`val`)
                } else {
                    levelValues.add(0, node.`val`)
                }
                
                node.left?.let { queue.offer(it) }
                node.right?.let { queue.offer(it) }
            }
            
            result.add(levelValues)
            level++
        }
        
        return result
    }
}

                                            
package main

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

func zigzagLevelOrder(root *TreeNode) [][]int {
    if root == nil {
        return [][]int{}
    }
    
    var result [][]int
    queue := []*TreeNode{root}
    level := 0
    
    for len(queue) > 0 {
        levelSize := len(queue)
        levelValues := make([]int, levelSize)
        
        for i := 0; i < levelSize; i++ {
            node := queue[0]
            queue = queue[1:]
            
            index := i
            if level % 2 == 1 {
                index = levelSize - 1 - i
            }
            levelValues[index] = node.Val
            
            if node.Left != nil {
                queue = append(queue, node.Left)
            }
            if node.Right != nil {
                queue = append(queue, node.Right)
            }
        }
        
        result = append(result, levelValues)
        level++
    }
    
    return result
}

                                            
# Definition for a binary tree node.
# class TreeNode
#     attr_accessor :val, :left, :right
#     def initialize(val = 0, left = nil, right = nil)
#         @val = val
#         @left, @right = left, right
#     end
# end

def zigzag_level_order(root)
    return [] if root.nil?
    result = []
    queue = [root]
    zigzag = false
    
    until queue.empty?
        level_size = queue.size
        level_values = []
        
        level_size.times do
            node = queue.shift
            if zigzag
                level_values.unshift(node.val)
            else
                level_values << node.val
            end
            queue << node.left if node.left
            queue << node.right if node.right
        end
        
        result << level_values
        zigzag = !zigzag
    end
    
    result
end

                                            
/**
 * Definition for a binary tree node.
 * class TreeNode(_value: Int = 0, _left: TreeNode = null, _right: TreeNode = null) {
 * }
 */
object Solution {
    def zigzagLevelOrder(root: TreeNode): List[List[Int]] = {
        import scala.collection.mutable.Queue
        import scala.collection.mutable.ListBuffer
        
        if (root == null) return List()
        
        val result = ListBuffer[List[Int]]()
        val queue = Queue[TreeNode]()
        var level = 0
        
        queue.enqueue(root)
        while (queue.nonEmpty) {
            val levelSize = queue.length
            val levelValues = ListBuffer[Int]()
            
            0 until levelSize foreach { _ =>
                val node = queue.dequeue()
                if (level % 2 == 0) levelValues += node.value
                else levelValues.prepend(node.value)
                
                if (node.left != null) queue.enqueue(node.left)
                if (node.right != null) queue.enqueue(node.right)
            }
            
            result += levelValues.toList
            level += 1
        }
        
        result.toList
    }
}

To solve this coding challenge, we aim to traverse a binary tree in a zigzag manner where the nodes are visited from left to right at one level and from right to left at the next level, alternating between these orders for each level.

# Explanation:

The zigzag level order traversal, also known as "spiral order traversal," involves oscillating the direction of traversal at each level of the tree. To achieve this, we follow these steps:

Tree Node Structure : The binary tree is made up of nodes, each having a value and links to its left and right children.
BFS Traversal Mechanism : We use a Breadth-First Search (BFS) traversal mechanism which is commonly implemented using a queue. This allows us to traverse the tree level by level.
Zigzag Order : We need to track the traversal direction. We can use a boolean flag to switch directions at each level. When the flag is
True

, we traverse left to right, and when it is
False

, we traverse right to left.
Queue Management : At each level, we process all nodes in the queue (which represent nodes at the current level) and gather their values. If we are moving in reverse order for that level, we adjust the order of adding values accordingly.
Result Storage : For each level of traversal, store the results in a list. The final result will be a list of these lists where each list contains the values of nodes at that level.

The following is a more detailed step-by-step approach:

# Step-by-Step Explanation / Detailed Steps in Pseudocode:

Check if root is null : If the root is empty, return an empty list as there are no nodes to traverse.
Initialize data structures :

A result list to store the final output.
A queue to assist in BFS traversal initialized with the root node.
A flag to keep track of the traversal order, initially set to
False

(indicating we're starting left to right).

Begin BFS traversal :

While the queue is not empty:

Get the size of the current level (number of nodes in the queue).
Initialize an empty list to capture the current level's values.
Process each node at the current level:

Extract the node from the queue.
Add its value to the level list (prepend if flag is
True

for reverse order).
Add its children to the queue for the next level.

Append the current level's result to the result list.
Flip the traversal flag for the next level.

Return the result list .

Pseudocode:

                                            
# Function to perform zigzag level order traversal
Function ZigzagLevelOrderTraversal(BinaryTreeNode root):
    
    # Step 1: Check if the root is null
    If root is null:
        Return an empty list

    # Step 2: Initialize the result list and queue
    Initialize list result = []
    Initialize queue = [root]
    Initialize boolean leftToRight = False
    
    # Step 3: Start BFS traversal
    While queue is not empty:
        Initialize list levelNodes = []
        Initialize integer levelSize = length of queue
        
        # Step 4: Process nodes at the current level
        For i from 0 to levelSize - 1:
            Set currentNode = dequeue from queue
            
            # Step 5: Add currentNode value to levelNodes 
            If leftToRight is True:
                Add currentNode.value to end of levelNodes
            Else:
                Add currentNode.value to the beginning of levelNodes
                
            # Step 6: Add children of currentNode to queue for the next level
            If currentNode.left is not null:
                Enqueue currentNode.left in queue
            If currentNode.right is not null:
                Enqueue currentNode.right in queue
        
        # Step 7: Append the current level's nodes to result
        Append levelNodes to result
        
        # Step 9: Flip the traversal order for the next level
        leftToRight = Not leftToRight
        
    # Step 10: Return the result list
    Return result

This pseudocode provides a clear pathway for solving the zigzag level order traversal problem while including necessary comments to understand each step. Ensure to implement this logic in the desired programming language for actual execution.