merging two binary search trees

Question

Possible Duplicate:
How i can merge two binary trees

I'm new to trees codes and I've been asked to write a code for merging two binary search trees by writing a function

void mergeBst (BST & othertree)

This function will receive another Bst and insert all non- redundant values from that tree to the current tree so can you please tell me how to do that?

You take all the elements from one tree and add them to the other. — Lee Taylor, Jan 17 '13 at 23:10
Think about how you would merge two sorted ranges abstractly first. Then apply this thinking to trees. — Kerrek SB, Jan 17 '13 at 23:11
Here's a clue. Google for the words in the title of your question here and read what it finds. — Lee Meador, Jan 17 '13 at 23:14
I have lots of other functions to write and I'm working on them but in the merging code I have none — user1988805, Jan 18 '13 at 19:43

score 3 · Answer 1 · edited May 23 '17 at 12:08

3

Create two sorted list using two trees. This will be O(m+n).Then merge two sorted list maintaining order.(O(m+n)) Create composed tree using the merged list.(O(m+n))

Or simply for every node in the input tree, find the position to insert node into the source tree. Then insert it.

How i can merge two binary trees

How to merge two BST's efficiently?

edited May 23 '17 at 12:08

Community

1
1

answered Jan 17 '13 at 23:36

woryzower

956
3
15
22

Beta · Answer 2 · 2013-01-17T23:33:21.060

1

To merge tree B into tree A (A.mergeBst(B)):

Compare the root of B to the root of A.
If the root of B is greater, merge B.left into A, and the rest of B into A.right.
If it's less, merge B.right into A, and the rest of B into A.left.
If they're equal, merge B.left into A.left, B.right into A.right, and discard the root of B.

edited Jan 17 '13 at 23:33

answered Jan 17 '13 at 23:19

Beta

96,650
16
149
150

1

I don't think this will always yield the correct merge. Consider trees (1,2,3) with 2 as root and (1,3,5) with 3 as root. Your algorithm will have 1 appear twice. – jxh Jan 17 '13 at 23:27
@user315052: drat, you're right. Hang on... – Beta Jan 17 '13 at 23:31
I think your new algorithm is now much closer. But, you have to also consider that the result of a merge may cause the root value to change. So, for example, the step "merge the rest of B into A.right" may not be correct after the first step of "merge B.left into A". For that particular case, I would change the order of the merges. – jxh Jan 17 '13 at 23:42
@user315052: can you give an example that *requires* the root value to change? – Beta Jan 17 '13 at 23:50
The BST may be self-balancing (e.g. Red-Black or AVL). – jxh Jan 17 '13 at 23:50
@user315052: the OP made no requirement that the resultant tree be self-balancing. – Beta Jan 17 '13 at 23:52

Cedias · Answer 3 · 2013-01-18T00:06:06.947

0

Considering two Binary Search Trees:

Source - the BST on which you will iterate
Target - the BST you wish to add source's values

There is a pretty simple algorithm.

for each "values" in source search if they are in target if they are, discard them, if not insert them.

EDIT: by "iterate" i meant: http://en.wikipedia.org/wiki/Tree_traversal

Pre-order iteration:

Visit the root.
Traverse the left subtree.
Traverse the right subtree.

edited Jan 18 '13 at 00:06

answered Jan 17 '13 at 23:24

Cedias

904
10
19

Your answer is about as vague as the original question. What does it mean to iterate over a binary search tree, to "for each 'values'" in it? – David Gorsline Jan 17 '13 at 23:52

merging two binary search trees

3 Answers3