> For the complete documentation index, see [llms.txt](https://lei-d.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://lei-d.gitbook.io/leetcode/tree/103binary-tree-zigzag-level-order-traversal.md).

# 103\_Binary Tree Zigzag Level Order Traversal

## 103. Binary Tree Zigzag Level Order Traversal

Level: medium

Tag: tree, breadth-first search

## Question

```
Given a binary tree, return the zigzag level order traversal of its nodes' values. 
(ie, from left to right, then right to left for the next level and alternate between).
```

### Example 1

```
Input: 
    3
   / \
  9  20
    /  \
   15   7

Output: 
[
  [3],
  [20,9],
  [15,7]
]
```

### Idea (breadth-first search)

* For each level, find all the node value, append to the result as a list. **\[reverse the node values if it's in even level]**
* Have a temporary list to store all the left and right child for all the node in the level.

### Solution : breadth-first search

Time: $$O(n)$$

Space: $$O(n)$$

```python
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def zigzagLevelOrder(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """

        res = []
        if root == None:
            return res

        level = [root]
        # use 1 and -1 to denote odd and even level
        flag = 1
        while len(level) > 0:
            # For each level, find all the node value, append to the result as a list
            res.append([node.val for node in level][::flag])
            flag *= -1
            # a temporary list to store all the left and right child for all the node in the level
            temp = []
            # append left and right child if they are not None
            for node in level:
                if node.left != None:
                    temp.append(node.left)
                if node.right != None:
                    temp.append(node.right)
            level = temp

        return res
```