Binary Tree Zigzag Level Order
mediumTrees & BST II+20 XPTime limit 2s
Print the tree level by level, but snake through it: the first level (the root) from left to right, the second level from right to left, the third from left to right again, and so on.
Tree format. A binary tree is given on one line in level order (top to bottom, left to right), with null for a missing child — the same way most interview platforms show trees. Trailing nulls are left out, and an empty tree is the single word null. Example: 3 9 20 null null 15 7 is
3
/ \
9 20
/ \
15 7
Input: one tree.
Output: one line per level, or empty for an empty tree.
Constraints: 0 ≤ nodes ≤ 10⁴. The tree has at most 10⁴ nodes and its height is at most 500, so recursion is safe in every language.
Think about it: do an ordinary level-order BFS and reverse every second level before printing. Or, without reversing, use two stacks: popping a stack naturally flips the order — push children left-then-right on one level and right-then-left on the next.
Sample input 1
3 9 20 null null 15 7
Sample output 1
3 20 9 15 7
Sample input 2
1 2 3 4 5 6 7 8 9
Sample output 2
1 3 2 4 5 6 7 9 8
Read input from standard input and print the answer to standard output. Your code runs in a secure sandbox against the samples (Run) and hidden tests (Submit).