Skip to main content

Level-Order Tree Zigzag Collector

medium
TreeBreadth First SearchBinary TreeQueueBfs Level Order
Asked atAmazonMicrosoftBloombergMeta

Problem Description

Given the root of a binary tree, return a list of its node values collected level by level in a **zigzag** pattern: nodes at even-depth levels (0, 2, 4, …) are collected left-to-right, while nodes at odd-depth levels (1, 3, 5, …) are collected right-to-left.

**Example 1:**
```
Input: root = [4, 2, 7, 1, 3, 6, 9]
4
/ \
2 7
/ \ / \
1 3 6 9
Output: [[4], [7, 2], [1, 3, 6, 9]]
```

**Example 2:**
```
Input: root = [1]
Output: [[1]]
```

**Example 3:**
```
Input: root = []
Output: []
```

Constraints

  • The number of nodes is in the range [0, 2000]
  • -1000 <= Node.val <= 1000

Follow-up

Return the zigzag traversal using only a deque (without any explicit reverse calls) by carefully choosing which end to append children to.

Hints

Try the problem first. If you get stuck, you can reveal hints one at a time.

Solution

Leaderboard

No entries yet for python.

Be the first — submit an accepted solution.