Solved

# Merging of teo binary search tree

Posted on 2004-03-26
566 Views
Hi,

Can anybody help me to write a program in 'c' to merge the content of two binary search trees into one.and  what will be the time &stroage complexities  of that solution.

Thanks,
Amit Agrawal
0
Question by:agri_amit
[X]
###### Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

• Help others & share knowledge
• Earn cash & points
• Learn & ask questions
• 10
• 8
• 3

LVL 45

Expert Comment

ID: 10686654
Hi agri_amit,

Merging binary trees is not particularly difficult, I'll be glad to help.  But what do you mean by "binary search trees"?

Kent
0

Author Comment

ID: 10686736
Binary search tree is nothing but a kind of binary tree where content in tree are  sorted if we traverse either in pre/post/in order.

0

LVL 45

Expert Comment

ID: 10686873
Hi agri_amit,

Sorry -- my question wasn't asked very well....

Describe the rules of your two trees.  Can both trees contain the same results?  Can they contain some of the same results?  Will one tree be a subset of the other?

Kent
0

LVL 45

Expert Comment

ID: 10686899
do an inorder traversal on both BSTs and use merge sort algorith to construct a third new BST
0

Author Comment

ID: 10686924
Both trees can have independent set of values and  as both are BST(binary search tree), each node is in sorted order.

Does this explaination ,answer ur question?
0

Author Comment

ID: 10686942
Can u provide the code for same?
0

LVL 45

Accepted Solution

sunnycoder earned 50 total points
ID: 10686990
you mean the entire code .... I may write if I find time but chances are very thin ...

The algo is really simple ....

I presume that you have inorder traversal function which returns you one node at a time or all nodes in an array ...

merge_func( tree1, tree2 )
{
array1 =  inorder (tree1);
array2 = inorder (tree2);
mergesort (tree1, tree2);
}

there are plenty of implementations of mergesort on the web ... I hope you can utilize one
0

LVL 45

Expert Comment

ID: 10687016
Hi agri_amit,

Sorry, but this sounds like a homework assignment and the member are prohibited from doing homework for others.  We can help you to write your own.

I assume that you already have the code to build the BST.  If so, merging two trees is a piece of cake.

Using one tree as the 'base', scan the other tree node by node.  Every time you encounter a node, simply add it to the base tree.  The base tree will now include both trees.  (You can delete the second tree if you wish.)

My question(s) above were to see if there were a shortcut based on the data values.  It doesn't appear that there is.  Consider these two trees:

200
/  \
/    \
100     300

150
/  \
/    \
50    250

Neither tree can be grafted onto the other in such a way that order integrity is maintained.  Hence the need to traverse the nodes of one of the trees and add each node to the other tree.

Kent
0

LVL 45

Expert Comment

ID: 10687059
Kent has a point there ... If you have code for building a BST, all you need to do is read from one and insert into another
0

Author Comment

ID: 10701260
hi sunnycoder,

Now this is time , i would like to discuss its time & storage complexity.
Would you like to comment on the same ?

Regards,
Amit
0

LVL 45

Expert Comment

ID: 10701589
sure ... what do you have so far and what would you like to know ?
Which method did you adopt ?
0

Author Comment

ID: 10701617
I am using
merge_func( tree1, tree2 )
{
array1 =  inorder (tree1);
array2 = inorder (tree2);
mergesort (tree1, tree2);
}

So what will its time & storage complexity for the same.

0

LVL 45

Expert Comment

ID: 10701720
inorder traversals O(n)

merging  O(n)

how did you rebuild your tree from the merged array ?
0

Author Comment

ID: 10701750
Like an array.
suppose two sorted arrays are there(simulate it like we are traversing tree in inorder)
first element of array will be compared to other one.and resultant element will go to new array.
Accordingly point to next elemet in thearray , from which element has not been pcked.
Does this answer ir question.

0

LVL 45

Expert Comment

ID: 10701758
that will give you a sorted array .... your final target is a BST .... You need to construct a BST from that array .... How did you do that ?
0

Author Comment

ID: 10701796
Is it not possible , to insert element in its proper position at the time of insertion.
I mean whenever we go for insertion , we will insert the node at its position and apply re-arrangment if required.

0

LVL 45

Expert Comment

ID: 10701834
you can exploit the fact that array is sorted ...

suppose array has n elements ...

let n/2 be the root .... n/4 be its left child and 3n/4 be its right child .... proceeding this way you can get a balanced tree in O(n)

the idea lends itself to recursion easily ...

given an array 0-n, let make n/2 as root and make a left subtree for 0-(n/2-1) a right subtree for n/2+1 to n
0

Author Comment

ID: 10701900
right, but you have included  the efforts required to rearrange tree as and when required.
It might be that for every node insertion , tree has to be revisit/reshuffled completly.

Am i right?
0

Author Comment

ID: 10701901
right, but you have not included  the efforts required to rearrange tree as and when required.
It might be that for every node insertion , tree has to be revisit/reshuffled completly.

Am i right?
0

LVL 45

Expert Comment

ID: 10701949
No, you wont have to reshuffle if you build it the way I said ... e.g.

3 7 10 22 34 66 87 120 139  is your sorted array of 9 elements ....

choose 5th element as root

34                          .... remaining elements [ 3 7 10 22 ]  [ 66 87 120 139 ]

going by above algorith choose 10 as left child and 120 as right child

34                  remaining elements [3 7] [22] [66 87] [139]
/       \
10            120
and so on ....

since your array is sorted, all elements to the left of ith element will be in the left subtree and all elements to the right of ith element will be in the right subtree ....

In light of this fact, you should be able to build the tree in O(n) without any reshuffling
0

Author Comment

ID: 10702052
right,
really did very appreciating effort.

Thanks for valuable help for this topic.

I am also running a question thread at
http://www.experts-exchange.com/Programming/Programming_Languages/C/Q_20933143.html.

If u like, we can have a disussion over that.

Regards,
Amit
0

## Featured Post

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

This tutorial is posted by Aaron Wojnowski, administrator at SDKExpert.net.  To view more iPhone tutorials, visit www.sdkexpert.net. This is a very simple tutorial on finding the user's current location easily. In this tutorial, you will learn hoâ€¦
This is a short and sweet, but (hopefully) to the point article. There seems to be some fundamental misunderstanding about the function prototype for the "main" function in C and C++, more specifically what type this function should return. I see soâ€¦
The goal of this video is to provide viewers with basic examples to understand and use while-loops in the C programming language.
The goal of this video is to provide viewers with basic examples to understand and use switch statements in the C programming language.
###### Suggested Courses
Course of the Month4 days, 13 hours left to enroll

#### 739 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.