**Prerequisites:** Binary Trees, Level order traversal, Queue.

**Problem:** Given a binary tree, print the zigzag level order traversal of its nodes.

(i.e., from left to right, then right to left for the next level and alternate between).

**Solution Approach:**

Solution to this problem is almost the same as that of level order traversal with a minor tweak. We keep a queue data structure to visit nodes at each level one by one. One more boolean variable, let’s name it leftToRight, is needed to keep track of ordering while printing/storing nodes at each level. If leftToRight is set to true, the algorithm store/print nodes at current

level from left to right, else, right to left.

**Time Complexity:** O(N), as we need to visit each node once.

**Space Complexity:** O(N), as we need to store each node in the queue so that later its children can be visited in a zigzag manner.