Reputation: 17
Given two binary search trees, is there an algorithm to combine them into a single binary search tree with linear time complexity?
I thought about putting the elements of the second tree into the first tree one by one but failed to achieve it in linear time complexity.
Upvotes: 0
Views: 344
Reputation: 18838
We know that if we have a sorted array, we can create the binary search tree in Theta(n)
. Also, we know that how to merge two sorted arrays (using merge procedure in the merge-sort in Theta(n)
). Now, Just create two sorted list from the current binary trees (see this solution) and merging them (see the merge
function from here). Then make the tree from the sorted result (see these code examples for this part).
As all steps are could be done in Theta(n)
, the final result would be in Theta(n)
, too.
Upvotes: 1
Reputation:
If the resulting tree can be any binary search tree, you can do just sort the elements of the 2 trees, and create a BST which is just a sort linked list of the elements.
One way of doing so is:
O(n)
time) merge
procedure from merge-sort (O(n)
time) O(n)
time) Upvotes: 4