# Binary Tree Zigzag Level Order Traversal

Sources: leetcode 103

Rating: medium

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).

```class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right

def zigzagLevelOrder(root: TreeNode) -> List[List[int]]:
# return the tree in zig zag level order
```

Solution

Iterate through the trees using a queue, starting with the root node and its level. Use a dictionary d to store information on each level with the level number being the keys and the list of node values being the value.

```def zigzagLevelOrder(root):
if root is None:
return []
queue = [(root, 0)]
d = {}
while queue:
node, level = queue.pop(0)
# iterate through tree
return [d[i] for i in range(len(d))]
```

If it is the first node of the level to be seen, create the new key. Otherwise, add the node value to the growing list of values. Then add the child nodes to the queue

```def zigzagLevelOrder(root):
if root is None:
return []
queue = [(root, 0)]
d = {}
while queue:
node, level = queue.pop(0)
if level in d:
d[level].append(node.val)
else:
d[level] = [node.val]
if node.left: queue.append((node.left, level+1))
if node.right: queue.append((node.right, level+1))
# rearrange to zig zag order
return [d[i] for i in range(len(d))]
```

Finally, go through the stored level order and reverse every other list to obtain zig zag order.

Final Code

```def zigzagLevelOrder(root):
if root is None:
return []
queue = [(root, 0)]
d = {}
while queue:
node, level = queue.pop(0)
if level in d:
d[level].append(node.val)
else:
d[level] = [node.val]
if node.left: queue.append((node.left, level+1))
if node.right: queue.append((node.right, level+1))
for k, v in d.items():
if k % 2 == 1:
v.reverse()
return [d[i] for i in range(len(d))]
```