Skills101
← All coding problems

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).

Loading editor…

Log in to run and submit your code — it's free.