Question

Suppose you have two binary search trees P and Q. Let P and Q be the number of elements inP and Q, and let hp and ho be the heights of P and Q. Assume that that is, hp ho < P IQ and A. Give a destructive algorithm for creating a binary search tree containing the union PUQ that runs in time O(|P2) in the worst case. B. Assume now that it is known that the largest element of P is less than the smallest element of Q.Give a destructive algorithm for creating a binary search tree containing the union PUQ that runs in time O(hp).

Answer 1

Question A.
We traverse tree P and add it's each element into Q one by one. There are |P| elements and adding each of them takes at most h_Q times and Q's height could become maximum h_Q + |P|, So in worst case we will need |P|(h_Q+|P|) operations which is equal to O(|P|²).
Question B.
If smallest element of Q is greater than largest element of P, we can just wind largest element in P and whole tree of Q as it's right child tree and union tree will still be binary search tree. Finding largest element in P takes at most h_P operations and adding child node is simple O(1) operation so we get time complexity O(h_P).

Comment down for any queries

Please give a thumb up