medium +25 pts

Zigzag Level Order Traversal

Return the level-order traversal of a binary tree in zigzag order.

Write a function `zigzag_level_order(root)` that takes the root of a binary tree and returns a list of lists, where each inner list contains the values of the nodes at that depth, with the direction alternating: at depth 0 (root) traverse left-to-right, at depth 1 traverse right-to-left, at depth 2 left-to-right, and so on. The tree is represented as nested dictionaries or `None`. Each dictionary has keys `val`, `left`, `right`. `left` and `right` are either `None` or a dict. The function receives a dict or `None` for an empty tree. If the tree is empty, return an empty list `[]`. The values are integers. The output must be a list of lists in order of increasing depth.

Constraints

The number of nodes in the tree is in the range [0, 2000]. -1000 <= val <= 1000 The solution should have O(n) time complexity, where n is the number of nodes.

Example

```python
>>> root = {'val': 3, 'left': {'val': 9, 'left': None, 'right': None}, 'right': {'val': 20, 'left': {'val': 15, 'left': None, 'right': None}, 'right': {'val': 7, 'left': None, 'right': None}}}
>>> zigzag_level_order(root)
[[3], [20, 9], [15, 7]]
```
```python
>>> zigzag_level_order(None)
[]
```
```python
>>> root = {'val': 1, 'left': {'val': 2, 'left': {'val': 4, 'left': None, 'right': None}, 'right': None}, 'right': {'val': 3, 'left': None, 'right': {'val': 5, 'left': None, 'right': None}}}
>>> zigzag_level_order(root)
[[1], [3, 2], [4, 5]]
```
25 points ~25 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Use a queue to traverse level by level (BFS). Keep track of the current depth to decide direction.
For even depth, append values from left to right; for odd depth, reverse the values or insert at the front.
A common pattern is to build each level's values in normal order and then reverse the list when needed.
Remember to handle the empty tree case early.
Python 3
All tests passed!
Test Results
Press Ctrl+Enter or click Run Tests to execute your code.