103. Binary Tree Zigzag Level Order Traversal 🚀
Tags: javascript, programming, tutorial, leetcode
Published: 2022-05-05 20:00:07

### Solution Developed In:
![JavaScript](https://img.shields.io/badge/javascript-%23323330.svg?style=for-the-badge&logo=javascript&logoColor=%23F7DF1E)

## The Question
For this article we will be covering Leetcode's '[103. Binary Tree Zigzag Level Order Traversal](https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal/submissions/)' question. 

Question:

> 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:

>![Example](https://assets.leetcode.com/uploads/2021/02/19/tree1.jpg)

```
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](https://leetcode.com/problems/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](https://leetcode.com/problems/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
1. [Binary Tree](https://en.wikipedia.org/wiki/Binary_tree)
2. [Depth First Search](https://en.wikipedia.org/wiki/Depth-first_search)
3. [Level order traversal](https://en.wikipedia.org/wiki/Level-order_traversal)
4. [102. Binary Tree Level Order Traversal](https://leetcode.com/problems/binary-tree-level-order-traversal/) (Able to do this with ease)
5. [Stack](https://en.wikipedia.org/wiki/Stack)

## What do we know?
1. We have a ***binary tree*** (Most times, it could be empty)
2. We need to store all the rows within the **Binary Tree** within a `array` that will represent the **level order traversal**
3. We need to perform [level order traversal](https://en.wikipedia.org/wiki/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](https://leetcode.com/problems/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**)* | Where ***n*** is the number of nodes in our ***Binary Tree*** | As we're going to traverse all of the nodes within the tree.
  
* Space Complexity: *O(**n**)* | Where ***n*** is the number of nodes in our ***Binary Tree*** | As we're going to add all of our nodes to a `level_order` array.

## Leetcode Results:

See Submission Link: 

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

[![LeetCode](https://img.shields.io/badge/LeetCode-000000?style=for-the-badge&logo=LeetCode&logoColor=#d16c06)](https://leetcode.com/submissions/detail/693200775/)


***

# 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;
};

```