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

For example: Given binary tree `[3,9,20,null,null,15,7]`
```     5
/  \
3    20
/ \
7   8
returns zig-zag order
[
[3],
[20,9],
[15,7]
]
```

The problem can be solved using BFS traversal. Start traversing the tree and move elements in a stack level by level. For each level insert into a list and depending on the level, have a flag to insert from start or end of the list.

`````` public class Solution {
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
List<List<Integer>> list = new ArrayList<List<Integer>>();
if (root == null)
return list;

int count = 1;
boolean leftToRight = true;
while (!stack.isEmpty()) {
int futureCount = 0;
while (count > 0) {
TreeNode t = stack.poll();
if (leftToRight) {
} else {
}
if (t.left != null) {
futureCount++;
}
if (t.right != null) {
futureCount++;
}
count--;
}
count = futureCount;
leftToRight = !leftToRight;
}
return list;
}

static class TreeNode {
TreeNode left;
TreeNode right;
int val;

public TreeNode(int value) {
this.val = value;
}
}}``````