116. Zig-Zag Level Order Traversal

Given a binary tree, print its nodes level by level, alternating direction each level: the root's level left-to-right, the next level right-to-left, the next left-to-right again, and so on. Print all values in this order, space-separated on one line. The tree is given as space-separated level-order tokens, where 'N' means no node there: the first token is the root, then for each node dequeued in level order you read its left-child token then its right-child token (if input runs out early, remaining children are treated as N).

Input: A single line of space-separated level-order tokens describing the binary tree ('N' marks an absent child). Output: Print all node values in zig-zag level order, space-separated on one line.

1 <= number of nodes <= 10^5

Whether depth 0 (the root's level) counts as 'even' or 'odd' for the reversal decision is the exact detail that determines which levels get reversed - always confirm this convention matches the problem's stated example before implementing.

Print a binary tree level by level, but alternate the reading direction each level: left-to-right, then right-to-left, then left-to-right again, and so on. Brute force: There isn't really a slower alternative here beyond the direct level-collection-and-selective-reversal approach - the only real implementation choice is whether to use two stacks (alternating which one is 'active') or a single queue with post-hoc reversal of alternating levels. Optimised: Collecting each level normally and only reversing every OTHER level's already-grouped list (rather than trying to traverse in alternating directions live) keeps the logic simple and correct - the standard BFS traversal itself never needs to change direction, only the post-processing of each level's collected list does.

Use two stacks, one for the current level and one for the next level. When popping nodes from the current-level stack (left to right or right to left alternately), push that node's children onto the next-level stack in an order chosen based on the current direction (left-then-right or right-then-left) so that popping the next stack automatically yields the correct zig-zag order for that level. This produces the zig-zag order directly during traversal rather than needing a reversal pass afterward, since the stack's LIFO order naturally reverses each level relative to the one before it. Time: O(n) Space: O(n)

Perform a standard breadth-first level-order traversal, collecting each level's node values into its own list from left to right as usual. After the entire traversal is done, go back and reverse every second list (level 1, level 3, ...) before printing. This is correct because it produces every level's values before deciding direction, but it does extra post-processing work of reversing lists after the fact rather than producing the zig-zag order directly during traversal. Time: O(n) Space: O(n)

Use one double-ended queue (deque) and a single direction flag. For each level, depending on the flag, either read nodes from front to back and append children to the back, or read from back to front and prepend children to the front, flipping the flag after every level. This achieves the same zig-zag ordering as the two-stack method but with a single unified data structure and simpler bookkeeping (no separate current/next containers to manage), making it the cleanest and most direct implementation of the traversal. Time: O(n) Space: O(n)

1. Perform a normal level-order (breadth-first) traversal, collecting each level's node values into its own separate list. 2. For every OTHER level (based on whether its depth is even or odd), reverse that level's list before combining everything. 3. Concatenate all the levels' lists together, in level order, to produce the final output.

Time: O(n) - every node is visited once during BFS, and each level's list is reversed at most once. Space: O(n) in the worst case, for the queue and the level-by-level result lists.

Test with a single-node tree, a tree with only two levels (checking the direction reversal), and a tree with 10^5 nodes for performance.

Be ready to mention the two-stack alternative (using one stack for left-to-right levels and another for right-to-left levels, swapping which is active each level) as a way to avoid an explicit reversal step - a nice alternative implementation to know.