Merging of teo binary search tree

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

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.

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

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

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?

Can u provide the code for same?

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

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

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

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

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.

inorder traversals O(n)

merging  O(n)

how did you rebuild your tree from the merged array ?

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.

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 ?

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.

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

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?

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?

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

right,
really did very appreciating effort.

Thanks for valuable help for this topic.

I am also running a question thread at
https://www.experts-exchange.com/questions/20933143/evaluate-an-expression-using-a-queue.html.

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

Regards,
Amit