Amazon Interview Question SDE1s
Country: United States
Interview Type: Phone Interview
//code without recursion
public static TreeNode trimBST(TreeNode root, int min, int max){
while(root != null) {
if(root.val > max) root= root.left;
else if (root.val < min) root = root.right;
else break;
}
//Now it takes care even if BST does not exist in range of min and max
if(root == null) return null;
Node temp =root;
//Now truncate the branch where node is < min
while (temp!= null) {
if(temp.left != null && temp.left .value < min) {
temp.left = null;
break;
}
}
temp =root;
//Now truncate the branch where node is > max
while (temp!= null) {
if(temp.right != null && temp.right .value > max) {
temp.right = null;
break;
}
}
return root;
}
If the order doesn't matter than just do inorder traversal of given BST to get sorted array. And create a new BST out of the valid range of numbers remaining in the sorted array.
--
If relationships need to be maintained
.
// call this function by passing the root node of given BST. This returns the new valid node that can be included in the BST
public Node nextValidNode(Node currNode)
if(currNode == null){
return null;
}
if(currNode.data < min){
// skip the left subtree and try to find next valid node in right subtree
return nextValidNode(currNode.right)
}else if(currNode.data > max){
//skip the right subtree and try to find next valid node in left subtree
return nextValidNode(currNode.left)
}else{
//include this node after setting its valid left and right child
currNode.left = nextValidNode(currNode.left);
currNode.right = nextValidNode(currNode.right);
return currNode;
}
Traverse the node in this way: Right sub tree, Left sub tree, Root.
Every time you reach the node, remove it from the tree and push it into a Stack.
At the end, the root node of the tree will be the top of the Stack.
Now start popping elements from the Stack and check if it falls within the specified range. If yes, then pass it to a method which constructs a BST.
Struct Node* trim(Struct Node* root,int min,int max)
{
if(root==NULL)
return NULL;
root->left=trim(root->left,min,max);
root_>right=trim(root->right,min,max);
if(root->data<min)
return root->right;
if(root->data>max)
return root->left;
}
However, you would be traversting the whole tree even tough you can avoid venturing into a subtree that wont be a part of the result.
struct Node *TrimBst(struct Node *&node,int min,int max)
{
if(!node)
return NULL;
if(node->data <min)
return TrimBst(node->right,min,max);
else if(node->data>max)
return TrimBst(node->left,min,max);
node->left=TrimBst(node->left,min,max);
node->right=TrimBst(node->right,min,max);
return node;
}
pbnode deleteRange(pbnode node,int min,int max)
{
if(node==NULL)
return NULL;
node->left = deleteRange(node->left,min,max);
node->right = deleteRange(node->right,min,max);
if((node->data < min)||(node->data > max))
{
if((node->right==NULL)&&(node->left==NULL))
{
delete(node);
return NULL;
}
else
if((node->right==NULL)||(node->left==NULL))
{
pbnode tnode = (node->right)?node->right:node->left;
delete(node);
return tnode;
}
else
{
pbnode tnode = node->right;
while(tnode->left!=NULL)
tnode = tnode->left;
int tdata = tnode->data;
node->data = tnode->data;
tnode->data = tdata;
node->right = deleteRange(node->right,min,max);
}
}
return node;
}
This is a classic recursive algorithm. The interviewer will want to see you puzzle it out, but the hint (as with all these interview questions) is that you should not write too much code.
Here is a solution in C++. It essentially creates another tree (thus keeping the original tree alone) within the defined range.
Node *range(Node *r, int s, int e) {
if (!r) return NULL;
Node *n = NULL;
if (r->val >= s && r->val <= e)
n = new Node(r->val);
if (n) {
n->left = range(r->left, s, e);
n->right = range(r->right, s, e);
} else {
if (r->val < s) n = range(r->right, s, e);
else n = range(r->left, s, e);
}
return n;
}
public class TrimBst {
public static class Node {
int value;
Node left;
Node right;
}
private Node root;
private Node trim(Node node, int min, int max) {
if (node == null) {
return null;
}
if (!(min <= node.value && node.value <= max)) {
node.left = trim(node.left, min, max);
node.right = trim(node.right, min, max);
} else if (node.value < min) {
return trim(node.right, min, max);
}
return trim(node.left, min, max);
}
public void trim(int min, int max) {
root = trim(root, min, max);
}
}
In Order traversal will do, with a slight twist.
public static void traversal(BinaryTreeNode root)
{
while(root.right != null && root.right.data > max )
{
//discard right nodes since they are greater than right anyways.
//and right is now greater than max.
root.right = root.right.left;
}
while(root.left != null && root.left.data < min)
{
//discard left nodes since they are smaller than left anyways.
//and left is now smaller than min.
root.left = root.left.right;
}
if(root.left != null)
traversal(root.left);
if(root.right != null)
traversal(root.right);
}
struct node * trimTree(struct node * root,int min,int max){
if(root == NULL){
return NULL;
}
root->left = trimTree(root->left,min,max);
root->right = trimTree(root->right,min,max);
if(root->data<min){
struct node * temp = root->right;
free(root);
return temp;
}
else if(root->data>max){
struct node * temp = root->left;
free(root);
return temp;
}
return root;
}
//Least common ancestor of given two node wold be required result.
int LCA(BinarySearchTree root, int node1, int node2){
if(root == null){
return -1;
}else{
if((root.data > node1 && root.data <node2) || (root.data< node1 && root.data > node2)){
return root.data;
}else{
if(node1 < node2){
if(node1 < root.data){
return LCA(root.left, node1, node2);
}else{
return LCA(root.right, node1, node2);
}
}else{
if(node2 < root.data){
return LCA(root.left, node1, node2);
}else{
return LCA(root.right, node1, node2);
}
}
}
}
}
We can do this by modifying the original BST.
1. Do a post order traversal of the tree.
2. For each node:
If its value is less than min or greater than max delete the node.
We can do this in O(n) time and O(1) space if each node has a reference to its parent.
Also by the time we reach a node, the node only has 0 or 1 child. So deletion is straight forward.
Here is some code to get you started. The deletion routine can be further reduced and optimized.
public void postOrder(TreeElement root) {
if (root == null) {
return;
}
postOrder(root.left);
postOrder(root.right);
if (root.data < this.MIN || root.data > this.MAX) {
System.out.println("delete " + root.data);
delete(root);
}
}
public void delete(TreeElement root) {
TreeElement parent = root.parent;
if(parent == null) {
if(root.left != null) {
this.root = root.left;
} else {
this.root = root.right;
}
return;
}
if (root.left == null && root.right == null) {
if (root == parent.left) {
parent.left = null;
} else {
parent.right = null;
}
} else if (root.left == null) {
if (root == parent.left) {
parent.left = root.right;
} else {
parent.right = root.right;
}
} else if(root.right == null) {
if (root == parent.left) {
parent.left = root.left;
} else {
parent.right = root.left;
}
} else {
// Should not happen
}
}
public static TreeNode trimBST(TreeNode root, int min, int max){
- Anonymous April 21, 2013if(root == null) return root;
if(root.data > max) return trimBST(root.left,min,max);
if(root.data < min) return trimBST(root.right,min,max);
root.left = trimBST(root.left,min,max);
root.right = trimBST(root.right,min,max);
return root;
}