How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Google.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Google during technical interviews.

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.

Input: ([],)

Expected Output: []

Explanation: An empty tree has no levels, so the result is an empty list.

Input: ([1, 2, 3, 4, 5, 6, 7],)

Expected Output: [[1], [3, 2], [4, 5, 6, 7]]

Explanation: A full tree of 7 nodes. Level 1 reverses 2,3 to 3,2; level 2 stays left-to-right.

Input: ([1, 2, None, 3, None, 4],)

Expected Output: [[1], [2], [3], [4]]

Explanation: A left-leaning chain (with nulls) — each level has a single node, so direction has no visible effect.

Input: ([5, 4, 8, 11, None, 13, 4, 7, 2, None, None, None, 1],)

Expected Output: [[5], [8, 4], [11, 13, 4], [1, 2, 7]]

Explanation: Asymmetric tree with internal nulls. Level 1 reverses to [8, 4]; level 3 reverses [7, 2, 1] to [1, 2, 7].

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.

Quick Overview

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.