# 103 Binary Tree Zigzag Level Order Traversal

Given a binary tree, return thezigzag level ordertraversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between).

For example:\
Given binary tree`[3,9,20,null,null,15,7]`,

```
    3
   / \
  9  20
    /  \
   15   7
```

return its zigzag level order traversal as:

```
[
  [3],
  [20,9],
  [15,7]
]
```

**Approach:**

We can first reduce this problem performing a level order traversal that meet the requirement of allocating a new vector per level. To do this, we follow two conditions. (1) If the element in the queue is null, then push in another nullptr. Here, we also know that the temporary 1d vector has finished its insertions, so it can be pushed back to the main 2d vector, and reset. Additionally, we flip a switch the tells is that the next insertion should be pushed back in reverse order. (2) Otherwise, do the usual bits of adding the left and right nodes.

**How it works:**

Consider the following tree:

```
        3
     9     20
 3      15      7
      20  23
```

We would follow roughly through the following process:

```
// initialize queue elements
push(3)
push(null)
   ^
top(3)
push children 9 and 20
   ^
top(null)
push(null) // which follows after 9 and 20
   ^
top(9)
push child 3
   ^
top(20)
push children 15 and 7
   ^
top(null)
push(null) // which follows after 3 15 and 7.
```

As we can see, every null that follows will be appropriate.

**Limitations**

Pushing back to the front of a vector is a bad idea! Ideally, I would have returned vector of lists.

```cpp
vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
    vector<vector<int>> zig_zag_lvl;
    vector<int> v_temp;
    if (!root) return zig_zag_lvl;

    bool insert_back = true;

    queue<TreeNode*> q;
    q.push(root);
    q.push(nullptr);

    while (!q.empty()) {

        TreeNode* cur_top = q.front();
        q.pop();

        if (cur_top) {
            if (insert_back) 
                v_temp.push_back(cur_top->val);
            else 
                v_temp.insert(v_temp.begin(), cur_top->val);

            if (cur_top->left)
                q.push(cur_top->left);
            if (cur_top->right)
                q.push(cur_top->right);
        }

        else {
            if (!q.empty())
                q.push(nullptr);

            zig_zag_lvl.push_back(v_temp);
            v_temp.clear();
            insert_back = !insert_back;
        }
    }

    return zig_zag_lvl;
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://maksimdan.gitbook.io/interview-practice-problems/leetcode_sessions/103-binary-tree-zigzag-level-order-traversal.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.