The following algorithm merges two binary search trees into one binary search tr
ID: 3801445 • Letter: T
Question
The following algorithm merges two binary search trees into one binary search tree. Let T1 and T2 be two BSTs such that T1 conatins n and T2 contains m integer values, where n>m>0. Below is a simple algorithm for merging T1 and T2:
a.) Describe the running time of this algorithm using big-O notation. Note that T1 contains n nodes and T2 contains m nodes, Therefore, your running time must be a function of both n and m. (First desrcibe the running time of each step, then compute overall running time)
b.)
Merge BST-V1 1 T 2 1. for each node node in T2 remove node from T2 insert the value of node into T 2. return TExplanation / Answer
a)
Removal of node from T2 will take O(log m) time
Insertion into T1 takes Log(n) in first iteration, then Log(n+1) in second, Log(n+2), Log(n+3)....and so on to Log(m+n-1) in the last iteration of for loop; This step takes O(Log(n))
The for loop will run m times
Since Log(n)>Log(m)
The algorithm will take O(m Log(n)) time
b)
MergeBST-V2(T1,T2)
1) Do inorder traversal of first tree and store the traversal in one temp array arr1[].
2) Do inorder traversal of second tree and store the traversal in another temp array arr2[].
3) The arrays created in step 1 and 2 are sorted arrays. Merge the two sorted arrays into one array of size m + n.
4) Construct a balanced tree from the merged array using the technique discussed in this post.
Step-1 takes O(m) time
Step-2 takes O(n) time
Step-3 takes O(m+n) time
Step-4 takes O(m+n) time
So the overall time complexity of algorithm is O(m+n)
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.