# Binary Tree Zigzag Level Order Traversal – Leetcode Solution

In this post, we are going to solve the 103. Binary Tree Zigzag Level Order Traversal problem of Leetcode. This problem 103. Binary Tree Zigzag Level Order Traversal is a Leetcode medium level problem. Let’s see the code, 103. Binary Tree Zigzag Level Order Traversal – Leetcode Solution.

## Problem

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

### 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`

Now, let’s see the code of 103. Binary Tree Zigzag Level Order Traversal – Leetcode Solution.

# Binary Tree Zigzag Level Order Traversal – Leetcode Solution

### 103. Binary Tree Zigzag Level Order Traversal – Solution in Java

```/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode() {}
*     TreeNode(int val) { this.val = val; }
*     TreeNode(int val, TreeNode left, TreeNode right) {
*         this.val = val;
*         this.left = left;
*         this.right = right;
*     }
* }
*/
class Solution {
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {

List<List<Integer>> outer = new ArrayList<List<Integer>>();
if(root == null) return outer;

boolean flag = false;

while(!q.isEmpty()){
List<Integer> inner = new ArrayList<Integer>();
int size = q.size();

while(size-- > 0){
TreeNode node = q.poll();
}

if(flag == false){
flag = true;
}else if(flag == true){
Collections.reverse(inner);
flag = false;
}

}
return outer;
}
}```

### 103. Binary Tree Zigzag Level Order Traversal – Solution in C++

```/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode() : val(0), left(nullptr), right(nullptr) {}
*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<vector<int> > zigzagLevelOrder(TreeNode* root) {
if (root == NULL) {
return vector<vector<int> > ();
}
vector<vector<int> > result;

queue<TreeNode*> nodesQueue;
nodesQueue.push(root);
bool leftToRight = true;

while ( !nodesQueue.empty()) {
int size = nodesQueue.size();
vector<int> row(size);
for (int i = 0; i < size; i++) {
TreeNode* node = nodesQueue.front();
nodesQueue.pop();

int index = (leftToRight) ? i : (size - 1 - i);

row[index] = node->val;
if (node->left) {
nodesQueue.push(node->left);
}
if (node->right) {
nodesQueue.push(node->right);
}
}

leftToRight = !leftToRight;
result.push_back(row);
}
return result;
}
};```

### 103. Binary Tree Zigzag Level Order Traversal– Solution in Python

```# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
def zigzagLevelOrder(self, root):
"""
:type root: TreeNode
:rtype: List[List[int]]
"""
if not root: return []
res, temp, stack, flag=[], [], [root], 1
while stack:
for i in xrange(len(stack)):
node=stack.pop(0)
temp+=[node.val]
if node.left: stack+=[node.left]
if node.right: stack+=[node.right]
res+=[temp[::flag]]
temp=[]
flag*=-1
return res
```

Note: This problem 103. Binary Tree Zigzag Level Order Traversal is generated by Leetcode but the solution is provided by CodingBroz. This tutorial is only for Educational and Learning purpose.