# LeetCode - Binary Tree Zigzag Level Order Traversal

## Problem statement

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

Problem statement taken from: https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal/

Example 1:

``````Input: root = [3, 9, 20, null, null, 15, 7]
Output: [[3], [20, 9], [15, 7]]
``````

Example 2:

``````Input: root = [1]
Output: [[1]]
``````

Example 3:

``````Input: root = []
Output: []
``````

Constraints:

``````- The number of nodes in the tree is in the range [0, 2000].
- -100 <= Node.val <= 100
``````

### Explanation

To traverse binary tree level by level we can refer our previous blog post here.

As per the problem statement, we need to traverse in zigzag fashion. We can achieve this by reversing the `tmp` array we create when a level is traversed completely.

Let's check the algorithm:

``````- initialize 2D array as vector vector<vector<int>> result
- initialize size and i
- set left to true

- return result if root == null

- initialize queue<TreeNode*> q
- push root to queue : q.push(root)

- initialize TreeNode* node for iterating on the tree

- loop while( !q.empty() ) // queue is not empty
- initialize vector<int> tmp
- set size = q.size()

- loop for i = 0; i < size; i++
- set node = q.front()

- if node->left
- push in queue: q.push(node->left)

- if node->right
- push in queue: q.push(node->right)

- remove the front node: q.pop()
- push node->val to tmp. tmp.push_back(node->val)

- left is false: if(!left)
- reverse(tmp.begin(), tmp.end())

- push the tmp to result: result.push_back(tmp)
- toggle left: left = !left

- return result
``````

#### C++ solution

``````class Solution {
public:
vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
vector<vector<int>> result;
int size, i;
bool left = true;

if(root == NULL)
return result;

queue<TreeNode* > q;
q.push(root);

TreeNode* node;

while(!q.empty()){
vector<int> tmp;
size = q.size();

for(i = 0; i < size; i++){
node = q.front();

if(node->left)
q.push(node->left);

if(node->right)
q.push(node->right);

q.pop();
tmp.push_back(node->val);
}

if(!left){
reverse(tmp.begin(), tmp.end());
}

result.push_back(tmp);
left = !left;
}

return result;
}
};``````

#### Golang solution

``````func reverse(array []int) []int {
for i, j := 0, len(array) - 1; i < j; i, j = i+1, j-1 {
array[i], array[j] = array[j], array[i]
}

return array
}

func zigzagLevelOrder(root *TreeNode) [][]int {
result := [][]int{}
left := true

queue := []*TreeNode{root}

for len(queue) != 0 {
tmp := []int{}
size := len(queue)

for i := 0; i < size; i++ {
if queue[0] != nil {
tmp = append(tmp, queue[0].Val)
queue = append(queue, queue[0].Left)
queue = append(queue, queue[0].Right)
}

queue = queue[1:]
}

if !left {
tmp = reverse(tmp)
}

result = append(result, tmp)
left = !left
}

return result[:len(result)-1]
}``````

#### Javascript solution

``````var zigzagLevelOrder = function(root) {
let result = [];
let queue = [];
let left = true;

if(root)
queue.push(root);

while(queue.length > 0) {
tmp = [];
let len = queue.length;

for (let i = 0; i< len; i++) {
let node = queue.shift();
tmp.push(node.val);

if(node.left) {
queue.push(node.left);
}

if(node.right) {
queue.push(node.right);
}
}

if( !left ) {
tmp = tmp.reverse();
}

result.push(tmp);
left = !left;
}

return result;
};``````

#### Dry Run

Let's dry-run our algorithm to see how the solution works.

``````Input: root = [3, 9, 20, null, null, 15, 7]

Step 1: vector<vector<int>> result
int size, i
left = true

Step 2: root == null
[3, 9..] == null
false

Step 3: queue<TreeNode*> q
q.push(root)

q = [3]

Step 4: loop !q.empty()
q = [3]
q.empty() = false
!false = true

vector<int> tmp
size = q.size()
= 1

for(i = 0; i < 1; i++)
- 0 < 1
- true

node = q.front()
node = 3

if node->left
- node->left = 9
- q.push(node->left)
- q = [3, 9]

if node->right
- node->right = 20
- q.push(node->right)
- q = [3, 9, 20]

q.pop()
q = [9, 20]

tmp.push_back(node->val)
tmp.push_back(3)

i++
i = 1

for(i < 1)
1 < 1
false

if !left
!left = false

result.push_back(tmp)
result = [[3]]
left = !left
= false

Step 5: loop !q.empty()
q = [9, 20]
q.empty() = false
!false = true

vector<int> tmp
size = q.size()
= 2

for(i = 0; i < 2; i++)
- 0 < 2
- true

node = q.front()
node = 9

if node->left
- node->left = nil
- false

if node->right
- node->right = nil
- false

q.pop()
q = [20]

tmp.push_back(node->val)
tmp.push_back(9)

i++
i = 1

for(i < 2)
- 1 < 2
- true

node = q.front()
node = 20

if node->left
- node->left = 15
- q.push(node->left)
- q = [20, 15]

if node->right
- node->left = 7
- q.push(node->right)
- q = [20, 15, 7]

q.pop()
q = [15, 7]

tmp.push_back(node->val)
tmp.push_back(20)
tmp = [9, 20]

i++
i = 2

for(i < 2)
- 2 < 2
- false

if !left
!left = true

reverse(tmp.begin(), tmp.end())
tmp = [20, 9]

result.push_back(tmp)
result = [[3], [20, 9]]
left = !left
= true

Step 6: loop !q.empty()
q = [15, 7]
q.empty() = false
!false = true

vector<int> tmp
size = q.size()
= 2

for(i = 0; i < 2; i++)
- 0 < 2
- true

node = q.front()
node = 15

if node->left
- node->left = nil
- false

if node->right
- node->right = nil
- false

q.pop()
q = [7]

tmp.push_back(node->val)
tmp.push_back(15)

i++
i = 1

for(i < 2)
- 1 < 2
- true

node = q.front()
node = 7

if node->left
- node->left = nil
- false

if node->right
- node->right = nil
- false

q.pop()
q = []

tmp.push_back(node->val)
tmp.push_back(7)
tmp = [15, 7]

i++
i = 2

for(i < 2)
- 2 < 2
- false

if !left
!left = false

result.push_back(tmp)
result = [[3], [20, 9], [15, 7]]

Step 7: loop !q.empty()
q = []
q.empty() = true
!true = false

Step 8: return result

So we return the result as [[3], [20, 9], [15, 7]].
``````