Amazon Interview Question
Software Engineer / DevelopersI might be wrong but I think each insert operation takes O(logn) and hence for n elements (n1 + n2) to be inserted in the new BST it takes O(n1+n2)log(n1+n2) ?
O(n) is correct. Think of mergesort, the complexity is O(nlogn) because of the merge operation(which is O(n)). In this case, you are creating a BST using something similar to mergesort but without the merge operation, so compexity is O(n).
@gevorgk : Question says binary tree not BST so inorder traversal will not guarantee you a sorted result...
Question says a very few things about the tree. It doesn't say wether the tree is sorted, wether the resulted tree have to be balanced etc. So assuming taht tree is not BST and the resulting tree shall not be balanced, the solution is just att the root of one tree as child to any leaf of another. I don't think that amazon could ask such a stupid question.
Is this right?
Do inorder traversal of both lists and store result in additional lists which will create 2 lists and then use merge sort to sort them. Time complexity will be O(nlogn).
Forgot to add then do insert operation for each node of the list to recreate the merged tree
Two binary search trees: T1 & T2
- I choose to break and insert T2 in T1.
- Find the max & min of T2
- Now run a insert in T1 with range (min, max) and if you are able to reach a leaf node then stick T2 as child of that leaf node
- If you are not able to find such a leaf noe and the search terminates at some internal node (whose value should be greater than 'min' and less than 'max') then
- break T2 into root, left sub-tree, right sub-tree
- insert T2's root in T1
- call recursively for left sub-tree
- call recursively for right sub-tree
Best case running time : O(log n1) + O(log n2)
Worst case - didnt compute
Why not we directly traverse each node of T2 using inorder and insert it in T1 using binary tree creation method?
its simples isnt it?
Here tree is ordinary binary tree and not the binary search tree. So we can attach the second tree to any of the node in which left child or right child is null.
Here assume that we will attach the second tree as a left child in first tree.
tree_node_type * merge_tree(tree_node_type *t1 , tree_node_type *t2)
{
tree_node_type *temp;
if(t1==NULL)
return t2;
if(t2==NULL)
return t1;
temp=t1;
while(temp->left)
temp=temp->left;
temp->left=t2;
return t1;
}
for complete c program see
"goursaha.freeoda.com/DataStructure/MergeTwoTree.html"
Assume the trees are BST. We are not told anything else, we dont know how balanced they are. How many nodes there are. To merge them, why not just do an inorder on one tree and insert on the second tree as we go?
Yes the inorder will give you sorted elements but by inserting directly to the second tree, you should get a fairly good result meaning, that we wont affect the second tree as much...
I dont know, I see so many complicated solutions, using extra structures, but I still dont see how those solutions are good if we are not given more information about the trees.
I know the big O is bad for this solution, since you have O(Nx log(N+M)) or something like that. But at the same time we are not using any extra space.... what do you think? I just want to know.
1. Create two sorted arrays by inorder traversing two trees - linear time
- gevorgk May 19, 20102. Merge two sorted arrays - linear time
3. Build BST from sorted array
Last step can be done in linear time by taking root node from the middle of array, and calling taking left and right chilfren recursively from left and right sub-arrays.
So the overall complexity is O(n)