Go Premium for a chance to win a PS4. Enter to Win

x
?
Solved

Merging of teo binary search tree

Posted on 2004-03-26
21
Medium Priority
?
569 Views
Last Modified: 2010-04-15
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
Comment
Question by:agri_amit
  • 10
  • 8
  • 3
21 Comments
 
LVL 46

Expert Comment

by:Kent Olsen
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

by:agri_amit
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 46

Expert Comment

by:Kent Olsen
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
Concerto Cloud for Software Providers & ISVs

Can Concerto Cloud Services help you focus on evolving your application offerings, while delivering the best cloud experience to your customers? From DevOps to revenue models and customer support, the answer is yes!

Learn how Concerto can help you.

 
LVL 45

Expert Comment

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

Author Comment

by:agri_amit
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

by:agri_amit
ID: 10686942
Can u provide the code for same?
0
 
LVL 45

Accepted Solution

by:
sunnycoder earned 200 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 46

Expert Comment

by:Kent Olsen
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

by:sunnycoder
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

by:agri_amit
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

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

Author Comment

by:agri_amit
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

by:sunnycoder
ID: 10701720
inorder traversals O(n)

merging  O(n)

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

Author Comment

by:agri_amit
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

by:sunnycoder
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

by:agri_amit
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

by:sunnycoder
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

by:agri_amit
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

by:agri_amit
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

by:sunnycoder
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

by:agri_amit
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

Industry Leaders: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

Question has a verified solution.

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

Preface I don't like visual development tools that are supposed to write a program for me. Even if it is Xcode and I can use Interface Builder. Yes, it is a perfect tool and has helped me a lot, mainly, in the beginning, when my programs were small…
Summary: This tutorial covers some basics of pointer, pointer arithmetic and function pointer. What is a pointer: A pointer is a variable which holds an address. This address might be address of another variable/address of devices/address of fu…
The goal of this video is to provide viewers with basic examples to understand and use structures in the C programming language.
The goal of this video is to provide viewers with basic examples to understand opening and writing to files in the C programming language.
Suggested Courses

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

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

Join & Ask a Question