# Level Order Alternating - Amazon Top Interview Questions

### Problem Statement :

```Given a binary tree root, return values of the nodes in each level, alternating from going left-to-right and right-to-left.

Constraints

n ≤ 100,000 where n is the number of nodes in root

Example 1

Input

root = [3, [0, null, [2, [1, null, null], null]], [4, null, null]]

Output

[3, 4, 0, 2, 1]```

### Solution :

```                        ```Solution in C++ :

vector<int> solve(Tree* root) {
vector<int> v;
stack<Tree*> st1, st2;
st1.push(root);
Tree* curr;
while (!st1.empty() or !st2.empty()) {
while (!st1.empty()) {
curr = st1.top();
st1.pop();
v.push_back(curr->val);
if (curr->left) {
st2.push(curr->left);
}
if (curr->right) {
st2.push(curr->right);
}
}
while (!st2.empty()) {
curr = st2.top();
st2.pop();
v.push_back(curr->val);
if (curr->right) {
st1.push(curr->right);
}
if (curr->left) {
st1.push(curr->left);
}
}
}
return v;
}```
```

```                        ```Solution in Python :

class Solution:
def solve(self, root):
d = deque()
d.append(root)
ans = []
lr = True
while d:
levelSize = len(d)
level = []
while levelSize:
current = d.popleft()
level.append(current.val)
if current.left:
d.append(current.left)
if current.right:
d.append(current.right)
levelSize -= 1
if lr:
ans += level
else:
ans += level[::-1]
lr = not lr
return ans```
```

## Insert a node at a specific position in a linked list

Given the pointer to the head node of a linked list and an integer to insert at a certain position, create a new node with the given integer as its data attribute, insert this node at the desired position and return the head node. A position of 0 indicates head, a position of 1 indicates one node away from the head and so on. The head pointer given may be null meaning that the initial list is e

## Delete a Node

Delete the node at a given position in a linked list and return a reference to the head node. The head is at position 0. The list may be empty after you delete the node. In that case, return a null value. Example: list=0->1->2->3 position=2 After removing the node at position 2, list'= 0->1->-3. Function Description: Complete the deleteNode function in the editor below. deleteNo

## Print in Reverse

Given a pointer to the head of a singly-linked list, print each data value from the reversed list. If the given list is empty, do not print anything. Example head* refers to the linked list with data values 1->2->3->Null Print the following: 3 2 1 Function Description: Complete the reversePrint function in the editor below. reversePrint has the following parameters: Sing