# Inorder Traversal - Amazon Top Interview Questions

### Problem Statement :

```Given a binary tree root, return an inorder traversal of root as a list.

Bonus: Can you do this iteratively?

Constraints

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

Example 1

Input

root = [1, null, [159, [80, null, null], null]]

Output

[1, 80, 159]```

### Solution :

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

vector<int> solve(Tree* root) {  // Morris traversal - Time: O(N), Space: O(1)
vector<int> inorder;

while (root) {
if (root->left) {
Tree* predecessor = root->left;
while (predecessor->right && predecessor->right != root)
predecessor = predecessor->right;

if (predecessor->right) {
inorder.push_back(root->val);
root = root->right;
predecessor->right = nullptr;
} else {
predecessor->right = root;
root = root->left;
}
} else {
inorder.push_back(root->val);
root = root->right;
}
}

return inorder;
}```
```

```                        ```Solution in Java :

import java.util.*;

/**
* public class Tree {
*   int val;
*   Tree left;
*   Tree right;
* }
*/
class Solution {
public int[] solve(Tree root) {
List<Integer> list = new ArrayList<>();
list = inOrder(root, new ArrayList<>());
int[] arr = new int[list.size()];
for (int i = 0; i < list.size(); i++) {
arr[i] = list.get(i);
}
return arr;
}
public List<Integer> inOrder(Tree root, List<Integer> list) {
if (root == null)
return list;
Stack<Tree> st = new Stack<>();
Tree temp = root;
while (temp != null || st.size() > 0) {
while (temp != null) {
st.push(temp);
temp = temp.left;
}

temp = st.pop();
temp = temp.right;
}
return list;
}
}```
```

```                        ```Solution in Python :

class Solution:
def solve(self, root):
if not root:
return []
# iteratively
stack = [root.right, root.val, root.left]
traversal = []

while stack:
currNode = stack.pop()
if type(currNode) == int:
traversal.append(currNode)
elif currNode is None:
continue
else:
stack.extend([currNode.right, currNode.val, currNode.left])

return traversal```
```

## View More Similar Problems

Given a pointer to the head of a linked list, insert a new node before the head. The next value in the new node should point to head and the data value should be replaced with a given value. Return a reference to the new head of the list. The head pointer given may be null meaning that the initial list is empty. Function Description: Complete the function insertNodeAtHead in the editor below

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