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.