Implement zigzag level-order traversal
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Given the root of a binary tree, return the node values in zigzag level order: visit nodes level by level, reading the first level from left to right, the next from right to left, and so on alternating each level. Output a list of lists of integers where each inner list contains the values for one level in the required direction. Aim for O(n) time and O(w) extra space, where n is the number of nodes and w is the maximum width of the tree.
Quick Answer: This question evaluates understanding of binary tree traversal, level-order processing with alternating directions, and the ability to reason about data structures and time/space complexity within the Coding & Algorithms domain.
Given the root of a binary tree, return the node values in zigzag level order: visit the tree level by level, reading the first (root) level from left to right, the next level from right to left, and continue alternating direction for each subsequent level. Return a list of lists of integers, where each inner list holds the values for one level in the required direction.
The tree is provided as a level-order array using `null` placeholders for absent children (the same encoding LeetCode uses), e.g. `[3, 9, 20, null, null, 15, 7]` represents a root `3` with children `9` and `20`, where `20`'s children are `15` and `7`. Reconstruct the tree from this array, then produce the zigzag traversal.
Target O(n) time and O(w) extra space, where n is the number of nodes and w is the maximum width of the tree.
Constraints
- The number of nodes is in the range [0, 2000].
- Node values fit in a 32-bit signed integer.
- The input array uses null placeholders for missing children and is a valid level-order encoding of a binary tree.
- An empty input array (or a leading null) represents an empty tree and returns an empty list.
Examples
Input: ([3, 9, 20, None, None, 15, 7],)
Expected Output: [[3], [20, 9], [15, 7]]
Explanation: Level 0 (L->R): [3]. Level 1 (R->L): nodes 9,20 read right-to-left -> [20, 9]. Level 2 (L->R): [15, 7].
Input: ([1],)
Expected Output: [[1]]
Explanation: A single node forms one level read left-to-right.
Hints
- The 'level by level' requirement is the signature of breadth-first search (BFS): process the tree one level at a time using a queue.
- For each level, record how many nodes are currently in the queue before you start popping — that count is exactly the size of the current level, so you can isolate one level per outer iteration.
- You do not need two stacks or special pushing order. Build each level left-to-right as usual, then simply reverse the level's value list whenever it should be read right-to-left.
- Track a boolean that flips after every level to decide whether the just-collected level needs to be reversed.