> For the complete documentation index, see [llms.txt](https://coding-9.gitbook.io/untitled/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://coding-9.gitbook.io/untitled/trees/binary-tree/medium/103.-binary-tree-zigzag-level-order-traversal.md).

# 103. Binary Tree Zigzag Level Order Traversal

## Problem Statement

<br>

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

&#x20;

**Example 1:**

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

<pre><code><strong>Input: root = [3,9,20,null,null,15,7]
</strong><strong>Output: [[3],[20,9],[15,7]]
</strong></code></pre>

**Example 2:**

<pre><code><strong>Input: root = [1]
</strong><strong>Output: [[1]]
</strong></code></pre>

**Example 3:**

<pre><code><strong>Input: root = []
</strong><strong>Output: []
</strong></code></pre>

&#x20;

**Constraints:**

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

## Intuition

```
```

### Links

<https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal/>

### Video Links

### Approach 1:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
class Solution {
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        vector<vector<int>> ans;
        if(root == NULL)
            return ans;

        queue<TreeNode*> q;
        q.push(root);
        bool flag = true;

        /*
        Basically just add the left and right to queue 
        just like Level order traversal

        Then based on flag just input in reverse or same order and go on
        */

        while (!q.empty()) {
            int size = q.size();
            vector<int> val(size);
            for(int i = 0; i < size; i++) {
                TreeNode *temp = q.front();
                q.pop();

                int index = (flag) ? i : (size-1-i);
                // Logic to input in reverse or same order

                val[index] = temp->val;
                if(temp->left != nullptr)   q.push(temp->left);
                if(temp->right != nullptr)   q.push(temp->right);
            }

            flag = !flag;
            //Change of flag after each iteration
            ans.push_back(val);
        }

        return ans;
    }
};
```

{% endcode %}

### Approach 2:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Approach 3:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Approach 4:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Similar Problems

###