Interview Question Software Engineer / Developers
0of 0 votesHow to merge the 2 BST,
in 1) O(n)
in 2) O(log n)
?
Country: -
Interview Type: Phone Interview
@ ali baba i think you want to do inorder traversal for getting sorted sequences , preorder traversal is not going to give sorted sequence.
"O(m+n) - time for BST algo to construct a BST"
Doesn't this require O(nlogn) time instead of O(m+n)? Correct me please if I am wrong?
For doing this in O(logn) time, can't we just traverse the smaller BST, and insert the data into the larger one?
Flatten the two BST's by traveling inorder and store the results in arrays.
merge two arrays.
build a BST with the merged array.
In order traversal of a tree takes O(n) time. Your approach will take approximately O(nlogn) time. The interviewer asked for a O(logn) time algo.
Can't we just insert one BST in another BST like we insert a new element in BST.
It will take O(logn) time and also the BST property will be maintained in final tree
No because for n elements of one tree the complexity would become O(nlogn); unless first binary tree contains elements in order O(c).
@bagarwal I think your method could work.........just insert the topmost element of 1 BST to another BST.....this can be done in O(log(n)) time.......and let the remaining elements attached to that element...
No suppose we have a(T1,T2) and b(T3,T4) as 2 BSTs with a and b as roots and Ti's as child BSTs.
Now suppose b is less than a then b is inserted somewhere in T1. Now if we just add T3 and T4 below b in T1 maybe an element of T4 could come that is greater than a which would violate the BST property
Find the preorder traversal of both lists , this gives the list in ascending order.
- Ali_BABA July 09, 2012Copy it in an array and then call BST with the array
Running time
O(n) + O(m) + c(m+n) + O(m+n)
where n- no of elements in tree 1
m= no of elements in tree2
c- constant time to copy each element to an array
O(m+n) - time for BST algo to construct a BST