#### Zigzag Traversal

A
```package com.thealgorithms.datastructures.trees;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

/**
* Given a binary tree.
* This code returns the zigzag level order traversal of its nodes' values.
* Binary tree:
*                               7
*                   /                         \
*                6                           3
*         /                \             /             \
*      2                    4         10                19
* Zigzag traversal:
* [[7], [3, 6], [2, 4, 10, 19]]
* <p>
* This solution implements the breadth-first search (BFS) algorithm using a queue.
* 1. The algorithm starts with a root node. This node is added to a queue.
* 2. While the queue is not empty:
*  - each time we enter the while-loop we get queue size. Queue size refers to the number of nodes
* at the current level.
*  - we traverse all the level nodes in 2 ways: from left to right OR from right to left
*    (this state is stored on `prevLevelFromLeftToRight` variable)
*  - if the current node has children we add them to a queue
*  - add level with nodes to a result.
* <p>
* Complexities:
* O(N) - time, where N is the number of nodes in a binary tree
* O(N) - space, where N is the number of nodes in a binary tree
*
* @author Albina Gimaletdinova on 11/01/2023
*/
public final class ZigzagTraversal {
private ZigzagTraversal() {
}
public static List<List<Integer>> traverse(BinaryTree.Node root) {
if (root == null) {
return List.of();
}

List<List<Integer>> result = new ArrayList<>();

// create a queue
Deque<BinaryTree.Node> q = new ArrayDeque<>();
q.offer(root);
boolean prevLevelFromLeftToRight = false;

while (!q.isEmpty()) {
int nodesOnLevel = q.size();
// traverse all the level nodes
for (int i = 0; i < nodesOnLevel; i++) {
BinaryTree.Node node = q.poll();
if (prevLevelFromLeftToRight) {
} else {
}
if (node.left != null) {
q.offer(node.left);
}
if (node.right != null) {
q.offer(node.right);
}
}
// the next level node traversal will be from the other side
prevLevelFromLeftToRight = !prevLevelFromLeftToRight;