Given a binary tree, a "zigzag" level order traversal prints the nodes level by level, but alternating the order of nodes from left-to-right and right-to-left for successive levels.     For example, Level 0 (root) is L-R, Level 1 is R-L, Level 2 is L-R, and so on.     Consider the following binary tree:     ```           3          / \         9  20           /  \          15   7     ```     What is the output of a zigzag level order traversal for this tree? 

Solution

A zigzag level order traversal alternates the direction of traversal for each level.            Level 0 (Left-to-Right): `3`            Level 1 (Right-to-Left): Children of `3` are `9` (left) and `20` (right). In right-to-left order: `20, 9`.            Level 2 (Left-to-Right): Children of `20` are `15` (left) and `7` (right). In left-to-right order: `15, 7`. (Node `9` has no children in this example).         Combining these, the output is `3, 20, 9, 15, 7`.