Amazon Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: In-Person
Why sort the array? If you're going to make a balanced tree, you can skip that step. If it's just a BST and you want to make sure it's balanced even without balancing mechanisms, then sorting it would be appropriate, of course.
Okay, so after a lot of thinking, I guess I could finally crack it ..
The idea is ... if we have two BSTs, we can merge them in-place, by just changing the pointers.
A tree with a single node is a BST.
1) Travel to the left most leaf node, keeping a pointer to its parent. make this node as new root of the BST that we are going to build. and set parent->left = null;
We can take any leaf node. I'm not checking of diff cases, where say is tree is right skewed. If someone can take the initiative of adding that code .. I'l be grateful :-)
node* getNewRoot(node* root){
node* parent = root;
node* newRoot = root->left;
while(!((newRoot->left==null)&&(newRoot->right ==null))) {
parent = newRoot;
newRoot = newRoot->left;
}
parent->left = null;
return newRoot;
}
2) Traverse the remaining binary tree in port-order. and keep inserting nodes in the BST with newRoot as root. The key is, after you insert a node in the BST, set its left and right pointers to null, so that this node is 'removed' from the old tree.
void convertIntoBST (node* curr){
if(!curr)
return;
convertIntoBST(curr->left);
convertIntoBST(curr->right);
InsertintoBST(newRoot, curr);
curr->left=null;
curr->right=null;
}
void InsertIntoBST(node* root, node* curr){
while(!((root->left == null)&&(root->right == null))) //iterate until root is not leaf node
{
if(root->val > curr->val)
root = root->left;
else
root = root->right;
}
if(root->val > curr->val)
root->left = curr;
else
root->right = curr;
}
This converts the same binary tree into a BST, by changing the pointers. No new node is created.
How ever time complexity is larger than O(n). Can someone tell what ?
Tree with single node is NOT BST... for any node left data
will be smaller and right data will be greater than the
node data, this is BST.
Binary Tree means, every node will have at most 2 nodes but
that can be greater or smaller.
Hmmm okay, I might have messed up with the terminologies, but the solution still holds good ..
If i just think on this for 2 minutes this is a classic POST ORDER problem: THis should work here.
1) Make a recursive function int Find_MAX(tree* p,int x, bool op).
2) Make a recursive function int Find_MIN(tree* p,int x, bool opration).
3) Pass node val to Find_MAX(p->left, p->val) and inside find_max check if input x is less than current node's val. If yes send it furthur to Find Max. Else keep retval as x for now.
4) after getting MAX from Left subtree find Min from right subtree.
5) finally compare min from right subtree and retval from prev and return the bigger value if this operation was to a left child(can be found using bool opration) else return smaller value.
6) Make node as return value
traverse the binary tree and store elements in array. (n)
- Mandar November 06, 2011sort the array using merge sort. (nlogn)
build the bst using the array.
complexity nlogn.