### Solution Developed In:

## The Question

For this article we will be covering Leetcode's '103. Binary Tree Zigzag Level Order Traversal' question.

Question:

Given the

`root`

of a binary tree, return thezigzag level order traversalof its nodes' values. (i.e., from left to right, then right to left for the next level and alternate > between).

Example:

```
Input: root = [1,null,0,0,1]
Output: [1,null,0,null,1]
Explanation:
Only the red nodes satisfy the property "every subtree not containing a 1".
The diagram on the right represents the answer.
```

## Explaining The Question

This Question is rated **Medium**. Which I believe is accurate. In many ways this question is the successor to '102. Binary Tree Level Order Traversal'. If you are familiar with the question, you will be able to understand this question.

What we're being asked to do is the same as 102. Binary Tree Level Order Traversal. Although with a twist, we need to do it in a zigzag fashion. Meaning we need to alternate between left and right. Normally we would just go `left -> right`

. As if we was reading a book. Although in this questions we need to go `left -> right`

and then `right -> left`

. A literal **zig zag**.

Now this may seem difficult because we're going to have to create a unusual traversal but it's actually not that difficult. We both know that level order traversal requires a `queue`

to store the `row`

nodes. All we need to do is to alternate the `queue`

between being a `queue`

and a `stack`

.

So whenever we add to the `row`

of the we also ask? **Do i add this value to the start or the end of the array?** That's it. π

## Recommended Knowledge

- Binary Tree
- Depth First Search
- Level order traversal
- 102. Binary Tree Level Order Traversal (Able to do this with ease)
- Stack

## What do we know?

- We have a
(Most times, it could be empty)*binary tree* - We need to store all the rows within the
**Binary Tree**within a`array`

that will represent the**level order traversal** - We need to perform level order traversal on the
**Binary Tree**but in a zigzag fashion.

## How we're going to do it:

We're going to be implementing a similar solution to the 102. Binary Tree Level Order Traversal question. Which is to use a `queue`

to store the `row`

nodes. Ensuring we have always cleared all the nodes in the `queue`

moving onto the next row.

The key difference here is we have a flag set called `zigzag`

to alternate between `true`

and `false`

values. True indicates we need to go `right -> left`

and false indicates we need to go `left -> right`

. We do this using the `unshift`

and `push`

methods.

Whenever we need to add a node to the `row`

we ask? **Do i add this value to the start or the end of the array?**. So if the `zigzag`

flag is `true`

we add the node to the start of the array using the `unshift`

operation like we would if this was a `queue`

. If the `zigzag`

flag is `false`

we add the node to the end of the array as if it was a `stack`

.

So what we achieve in the end isn't `zigzag`

traversal but something that mimics it. Technically speaking, we are traversing the `Binary Tree`

in a `level order`

fashion. But the way we add the nodes to the `row`

is in a `zigzag`

fashion.

## Big O Notation:

Time Complexity:

*O(**n**)*| Whereis the number of nodes in our*n*| As we're going to traverse all of the nodes within the tree.*Binary Tree*Space Complexity:

*O(**n**)*| Whereis the number of nodes in our*n*| As we're going to add all of our nodes to a*Binary Tree*`level_order`

array.

## Leetcode Results:

See Submission Link:

- Runtime: 69 ms, faster than
of JavaScript online submissions for Binary Tree Zigzag Level Order Traversal.*76.64%* - Memory Usage: 43.5 MB, less than
of JavaScript online submissions for Binary Tree Zigzag Level Order Traversal.*95.97%*

# The Solution

```
var zigzagLevelOrder = function (root) {
// What we do here is perform the normal
// level order traversal in rows.
// But we instead use a stack / queue depending
// on if we're to zig zag or not.
// Base case, we have no root.
if (!root) {
return [];
}
// So we're going to need a queue for the level order traversal.
// We're also going to need a level_order array to store all the rows
// of the binary tree
// as well as a flag to invert the order of the rows or not
// (zig zag). Meaning, if we're going to zig zag, we'll get the first node in the queue
// if we're not zig zag, we'll get the last node in the queue. (Unshift / pop)
let queue = [root];
let level_order = [];
let zigzag = true;
// So we perform a normal iterative level order traversal.
while (queue.length) {
// This will be our row, it will store all the nodes for the row in the tree
let row = [];
let queue_len = queue.length;
// So we're always going to invert the order of the rows.
// We do this to create our zig zag effect.
// Back, forward, back, forward, etc.
zigzag = !zigzag;
// We're going to get everything in the queue.
// at this particular moment and nothing more.
for (let counter = 0; counter < queue_len; counter++) {
// Grab the current node by removing it off the end of the queue
let node = queue.pop();
// So, if the invert flag is set, we're going to push the current node
// to the START of the row. Which means, we will produce a zig zag effect.
// Without having to change the order in which we visit our nodes.
// If the invert flag is not set, we're going to push the current node
// to the end of the row stack like we normally would in level order traversal.
if (zigzag) {
row.unshift(node.val);
} else {
row.push(node.val);
}
// Add to the queue.
node.left ? queue.unshift(node.left) : null;
node.right ? queue.unshift(node.right): null;
}
// Push to the level_order array.
level_order.push(row);
}
// Return the level_order array.
return level_order;
};
```

## Top comments (0)