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
View More Similar Problems
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
View Solution →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
View Solution →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
View Solution →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
View Solution →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.
View Solution →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
View Solution →