# Tree Shifting - Amazon Top Interview Questions

### Problem Statement :

```Given a binary tree root, shift all the nodes as far right as possible while maintaining the relative ordering in each level.

Constraints

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

Example 1

Input

root = [1, [2, [4, null, null], null], [3, [5, [6, null, null], [7, null, null]], null]]

Output

[1, [2, null, null], [3, [4, null, null], [5, [6, null, null], [7, null, null]]]]

Example 2

Input

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

Output

[1, null, [2, null, [3, null, [4, null, [5, null, null]]]]]

Example 3

Input

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

Output

[1, null, [2, null, [3, null, [4, null, [5, null, null]]]]]```

### Solution :

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

int lens(Tree* root) {
if (root == NULL) return 0;
return 1 + max(lens(root->left), lens(root->right));
}
void dfs(Tree* root, int lev, vector<vector<int>>& m) {
if (root == NULL) return;
m[lev].push_back(root->val);
dfs(root->left, lev + 1, m);
dfs(root->right, lev + 1, m);
}
Tree* build(vector<vector<int>>& m, int i) {
if (i >= m.size() or m[i].size() == 0) return NULL;
Tree* root = new Tree(m[i].back());
m[i].pop_back();
root->right = build(m, i + 1);
root->left = build(m, i + 1);
return root;
}
Tree* solve(Tree* root) {
vector<vector<int>> m(lens(root) + 1);
dfs(root, 0, m);
return build(m, 0);
}```
```

```                        ```Solution in Python :

class Solution:
def solve(self, root):
if root is None:
return None

level = [root]

while level:
child_level = []

for node in level:
if node.left:
child_level.append(node.left)
if node.right:
child_level.append(node.right)

child_index = len(child_level) - 1

for node in reversed(level):
node.right = child_level[child_index] if child_index >= 0 else None
child_index -= 1
node.left = child_level[child_index] if child_index >= 0 else None
child_index -= 1

level = child_level

return root```
```

## Tree: Preorder Traversal

Complete the preorder function in the editor below, which has 1 parameter: a pointer to the root of a binary tree. It must print the values in the tree's preorder traversal as a single line of space-separated values. Input Format Our test code passes the root node of a binary tree to the preOrder function. Constraints 1 <= Nodes in the tree <= 500 Output Format Print the tree's

## Tree: Postorder Traversal

Complete the postorder function in the editor below. It received 1 parameter: a pointer to the root of a binary tree. It must print the values in the tree's postorder traversal as a single line of space-separated values. Input Format Our test code passes the root node of a binary tree to the postorder function. Constraints 1 <= Nodes in the tree <= 500 Output Format Print the

## Tree: Inorder Traversal

In this challenge, you are required to implement inorder traversal of a tree. Complete the inorder function in your editor below, which has 1 parameter: a pointer to the root of a binary tree. It must print the values in the tree's inorder traversal as a single line of space-separated values. Input Format Our hidden tester code passes the root node of a binary tree to your \$inOrder* func

## Tree: Height of a Binary Tree

The height of a binary tree is the number of edges between the tree's root and its furthest leaf. For example, the following binary tree is of height : image Function Description Complete the getHeight or height function in the editor. It must return the height of a binary tree as an integer. getHeight or height has the following parameter(s): root: a reference to the root of a binary

## Tree : Top View

Given a pointer to the root of a binary tree, print the top view of the binary tree. The tree as seen from the top the nodes, is called the top view of the tree. For example : 1 \ 2 \ 5 / \ 3 6 \ 4 Top View : 1 -> 2 -> 5 -> 6 Complete the function topView and print the resulting values on a single line separated by space.

## Tree: Level Order Traversal

Given a pointer to the root of a binary tree, you need to print the level order traversal of this tree. In level-order traversal, nodes are visited level by level from left to right. Complete the function levelOrder and print the values in a single line separated by a space. For example: 1 \ 2 \ 5 / \ 3 6 \ 4 F