How to Merge Two Bst's Efficiently

algorithm - How to concatenate two binary search tree efficiently?

Let A be the smaller set. Assume x = maximum_element(A) and y = minimum_element(B).

We know x < y. take a node with key value equal to z = (x+y)/2 and make A its left subtree and B its right subtree. remove the added node(with key z) from this BST.

How i can merge two binary trees

Not considering efficiency this answer may work Algorithm of combining two binary trees? . If sorted or balanced, discussion on efficiency in How to merge two BST's efficiently? and Concatenating/Merging/Joining two AVL trees

Merging Binary search tree

If the trees are not balanced, or the result shouldn't be balanced that's quite easy:

without loss of generality - let the first BST be smaller (in size) than the second.
1. Find the highest element in the first BST - this is done by following the right son while it is still available. Let the value be x, and the node be v
2. Remove this item (v) from the first tree
3. Create a new Root with value x, let this new root be r
4. set r.left = tree1.root, r.right = tree2.root

(*) If the first BST is bigger in size than the second, just repeat the process for finding v as the smallest node in the second tree.

(*) Complexity is O(min{|T1|,|T2|}) worst case (finding highest element if the tree is very inbalanced), and O(log(min{|T1|,|T2|})) average case - if the tree is relatively balanced.

---

Related Topics