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.