# LeetCode: 103. Binary Tree Zigzag Level Order Traversal

**The 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**

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

**Constraints:**

- The number of nodes in the tree is in the range
`[0, 2000]`

. `-100 <= Node.val <= 100`

**Solution**

We opted for a recursive approach to tackle this problem, and upon evaluating our solution on the LeetCode platform, we achieved the following outcome:

Here's the code that led us to this result.

```
vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
vector<vector<int>> ans;
zigzagLevelOrder(root, ans, 0, true);
return ans;
}
void zigzagLevelOrder(TreeNode* &root, vector<vector<int>> &ans, int level, bool inverse) {
if(root == NULL) return;
int nextLevel = level + 1;
if(ans.size() < nextLevel) ans.resize(nextLevel);
if(inverse) ans[level].push_back(root->val);
else ans[level].insert(ans[level].begin(), root->val);
inverse = !inverse;
zigzagLevelOrder(root->left, ans, nextLevel, inverse);
zigzagLevelOrder(root->right, ans, nextLevel, inverse);
}
```

Here's a breakdown of the code:

1. The `zigzagLevelOrder`

function is the public entry point for the zigzag-level order traversal. It takes the binary tree's root node as input and initializes an empty vector of vectors (`ans`

) to store the result.

2. It calls the helper function `zigzagLevelOrder`

(the second function with the same name) to perform the traversal. The `level`

argument is initially set to 0, indicating the root level, and the `inverse`

argument is initially set to `true`

, indicating that the first level should be traversed from left to right.

3. In the helper `zigzagLevelOrder`

function:

- It checks if the current node (
`root`

) is NULL. If it is, it returns immediately, as there's nothing to process for this node. - It increments the
`nextLevel`

variable by 1 to represent the level below the current level. - It checks if the
`ans`

vector has fewer levels than`nextLevel`

. If so, it resizes`ans`

to accommodate the new level. - Depending on the
`inverse`

flag, it either appends the value of the current node (`root->val`

) to the vector corresponding to the current level (`ans[level]`

) or inserts it at the beginning of the vector, effectively reversing the order. - It toggles the
`inverse`

flag to reverse the traversal direction for the next level. - It recursively calls the
`zigzagLevelOrder`

function for the left and right children of the current node, passing`nextLevel`

and the updated`inverse`

value as arguments.

4. The `zigzagLevelOrder`

function is called initially from the public entry point with the root node and an empty `ans`

vector. As the traversal progresses, the `ans`

vector is filled with sub-vectors representing each level of the binary tree, with alternating directions for traversal.

5. Finally, the `ans`

vector, which now contains all the levels of the binary tree in a zigzag pattern, is returned as the result of the zigzag-level order traversal.