Solved

Merging of teo binary search tree

Posted on 2004-03-26
21
560 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 45

Expert Comment

by:Kdo
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 45

Expert Comment

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

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 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

by:Kdo
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
How to run any project with ease

Manage projects of all sizes how you want. Great for personal to-do lists, project milestones, team priorities and launch plans.
- Combine task lists, docs, spreadsheets, and chat in one
- View and edit from mobile/offline
- Cut down on emails

 
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

Why You Should Analyze Threat Actor TTPs

After years of analyzing threat actor behavior, it’s become clear that at any given time there are specific tactics, techniques, and procedures (TTPs) that are particularly prevalent. By analyzing and understanding these TTPs, you can dramatically enhance your security program.

Join & Write a Comment

Have you thought about creating an iPhone application (app), but didn't even know where to get started? Here's how: ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ Important pre-programming comments: I’ve never tri…
An Outlet in Cocoa is a persistent reference to a GUI control; it connects a property (a variable) to a control.  For example, it is common to create an Outlet for the text field GUI control and change the text that appears in this field via that Ou…
The goal of this video is to provide viewers with basic examples to understand how to use strings and some functions related to them 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.

759 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

Need Help in Real-Time?

Connect with top rated Experts

20 Experts available now in Live!

Get 1:1 Help Now