wu :: forums
« wu :: forums - Binary search tree merging »

Welcome, Guest. Please Login or Register.
Mar 19th, 2024, 4:12am

RIDDLES SITE WRITE MATH! Home Home Help Help Search Search Members Members Login Login Register Register
   wu :: forums
   riddles
   cs
(Moderators: Grimbal, Icarus, ThudnBlunder, towr, william wu, SMQ, Eigenray)
   Binary search tree merging
« Previous topic | Next topic »
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: Binary search tree merging  (Read 11728 times)
knuther
Newbie
*





   


Posts: 6
Binary search tree merging  
« on: Dec 9th, 2004, 1:04am »
Quote Quote Modify Modify

Got this question recently in an interview.....
 
There are two unbalanced binary search trees say T1 and T2. Find an efficient algorithm to merge these two trees into a (Height) Balanced Binary search tree T3.
 
Brute force algorithm would require O(n logm)+Time for balancing with n being number of nodes in T1 and m being number of nodes in T2. or O(m log n) + Balancing time.
 
 
can we  optimize on this using extra space?
IP Logged
towr
wu::riddles Moderator
Uberpuzzler
*****



Some people are average, some are just mean.

   


Gender: male
Posts: 13730
Re: Binary search tree merging  
« Reply #1 on: Dec 9th, 2004, 1:39am »
Quote Quote Modify Modify

::How about flattening both trees into array's of length n and m respectively, then merging them together into an n+m array, and rebuild a tree from that.
Building a balanced tree from sorted data is easy enough after all.
Should be O(n+m)
::
IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
puzzlecracker
Senior Riddler
****



Men have become the tools of their tools

   


Gender: male
Posts: 319
Re: Binary search tree merging  
« Reply #2 on: Dec 9th, 2004, 7:28am »
Quote Quote Modify Modify

how do you do that (flattening)?
IP Logged

While we are postponing, life speeds by
towr
wu::riddles Moderator
Uberpuzzler
*****



Some people are average, some are just mean.

   


Gender: male
Posts: 13730
Re: Binary search tree merging  
« Reply #3 on: Dec 9th, 2004, 8:24am »
Quote Quote Modify Modify

Put all the elements in the order that you encounter them in during a depth first traversal of the tree.
IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
John_Gaughan
Uberpuzzler
*****



Behold, the power of cheese!

5187759 5187759   john23874   SnowmanJTG
WWW Email

Gender: male
Posts: 767
Re: Binary search tree merging  
« Reply #4 on: Dec 10th, 2004, 1:55pm »
Quote Quote Modify Modify

I don't see how merging two flattened trees will optimize anything. Even with a mergesort on the arrays, that is O(log2n). Quicksort would be a crappy algorithm because the data is almost sorted. Combined with traversing a tree, O(n), and constructing a new one, O(nlog2n), there is no savings in time that I can see.
 
However, I seem to remember seeing another algorithm somewhere that might help. I will see if I can find it when I get home this afternoon.
IP Logged

x = (0x2B | ~0x2B)
x == the_question
towr
wu::riddles Moderator
Uberpuzzler
*****



Some people are average, some are just mean.

   


Gender: male
Posts: 13730
Re: Binary search tree merging  
« Reply #5 on: Dec 11th, 2004, 9:33am »
Quote Quote Modify Modify

on Dec 10th, 2004, 1:55pm, John_Gaughan wrote:
I don't see how merging two flattened trees will optimize anything. Even with a mergesort on the arrays, that is O(log2n).
They're allready sorted, so you only need to merge them.
 
traversing the trees and flattenign them is O(n) + O(m)=O(n+m)
Merging them is O(n+m)
Making a new balanced tree from the merged array is O(n+m)
So the total is O(n+m) which is better then O(n log m)
IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
knuther
Newbie
*





   


Posts: 6
Re: Binary search tree merging  
« Reply #6 on: Dec 11th, 2004, 8:29pm »
Quote Quote Modify Modify

TOWR is right.  
 
The tree flattening will yeild sorted arrays if inorder traversal is done for the binary search tree ( left -root - right). This is O(n) and O(m)
 
Then we have to merge these two arrays which is O(n+m).
 
Now we have to build a balanced binary search tree from the sorted array. This can probably be done by starting at the middle element and assigning it as root and recursively applying the same function to the left subarray of the element
getting the left subtree's  root and then to the right subarray of the element to get the right subtree's root.
 
The space overhead here is n+m(flattening)+n+m(merging...Inhouse merging is costly..)+n+m(building a balanced tree).
 
Can this be further optimized in terms of space consumed ?
 
IP Logged
towr
wu::riddles Moderator
Uberpuzzler
*****



Some people are average, some are just mean.

   


Gender: male
Posts: 13730
Re: Binary search tree merging  
« Reply #7 on: Dec 12th, 2004, 12:12pm »
Quote Quote Modify Modify

You don't have to explicitly flatten the trees before starting to merge them. You can do that while traversing both trees inorder.
And if you know how many elements there are, you can also start rebuilding the balanced tree without completing the merged array.. You would still need space to keep track of all the subtrees; I think that's in the order of the depth of the tree (at most one subtree for each level, because if you have two subtrees at one level they comprise a larger subtree at a higher level)
I probably wouldn't want to try that last optimalisation though, unless n+m was a power of two though..
« Last Edit: Dec 12th, 2004, 12:19pm by towr » IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
John_Gaughan
Uberpuzzler
*****



Behold, the power of cheese!

5187759 5187759   john23874   SnowmanJTG
WWW Email

Gender: male
Posts: 767
Re: Binary search tree merging  
« Reply #8 on: Dec 13th, 2004, 12:19pm »
Quote Quote Modify Modify

Ah, I see now. Doing a preorder traversal will, of course, get all elements in ascending order: O(n+m). Merging into another array is trivial: O(n+m). Creating another tree using knuther's method is O(n+m). So the whole thing is O(n+m). But to do this you need to make the tree manually, getting old school. No STL or other prebaked solution here Wink
 
Actually, to address knuther's other issue, we don't have to create three arrays. Merge the trees into the array on the fly while traversing using the same method as merging two sorted arrays, treating the output of the preorder traversals as serialized arrays.
 
If we know the size of the original trees, we can forgo the intermediate array entirely by calculating the structure of the target tree and inserting nodes directly where they will wind up. This only works, however, if we have a priori knowledge of the tree's size.
IP Logged

x = (0x2B | ~0x2B)
x == the_question
towr
wu::riddles Moderator
Uberpuzzler
*****



Some people are average, some are just mean.

   


Gender: male
Posts: 13730
Re: Binary search tree merging  
« Reply #9 on: Dec 13th, 2004, 12:33pm »
Quote Quote Modify Modify

yeah, that's what I said  Roll Eyes
IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
John_Gaughan
Uberpuzzler
*****



Behold, the power of cheese!

5187759 5187759   john23874   SnowmanJTG
WWW Email

Gender: male
Posts: 767
Re: Binary search tree merging  
« Reply #10 on: Dec 13th, 2004, 1:02pm »
Quote Quote Modify Modify

on Dec 13th, 2004, 12:33pm, towr wrote:
yeah, that's what I said  Roll Eyes

Maybe I should have read your post first. The best place to hide something from me is out in the open Grin
IP Logged

x = (0x2B | ~0x2B)
x == the_question
A
Full Member
***



Perder todas as esperanças é liberdade!

   


Gender: male
Posts: 236
Re: Binary search tree merging  
« Reply #11 on: May 24th, 2007, 7:02am »
Quote Quote Modify Modify

on Dec 12th, 2004, 12:12pm, towr wrote:
You don't have to explicitly flatten the trees before starting to merge them. You can do that while traversing both trees inorder.

Ok . I Understood this one  
 
on Dec 12th, 2004, 12:12pm, towr wrote:

And if you know how many elements there are, you can also start rebuilding the balanced tree without completing the merged array.. You would still need space to keep track of all the subtrees; I think that's in the order of the depth of the tree (at most one subtree for each level, because if you have two subtrees at one level they comprise a larger subtree at a higher level)
I probably wouldn't want to try that last optimalisation though, unless n+m was a power of two though..

 
But  i didnt get this one . Can U please give some pseudocode/example  
 Huh
IP Logged

What Doesn't Kill Me Will Only Make Me Stronger
towr
wu::riddles Moderator
Uberpuzzler
*****



Some people are average, some are just mean.

   


Gender: male
Posts: 13730
Re: Binary search tree merging  
« Reply #12 on: May 24th, 2007, 8:20am »
Quote Quote Modify Modify

on May 24th, 2007, 7:02am, R0B1N wrote:
But  i didnt get this one . Can U please give some pseudocode/example  
 Huh
You use recursion, and treat the elements from the merging as an incoming stream.
Since you know the number of elements (which was given as an assumption), you know how many need to go to the first subtree and how many in the next subtree. And recursively you know it for each subtree.
 
So, I suppose
Code:

 
buildtree(stream &mergedstream, int size)
{
  if (!size || !mergedstream)
    return 0;
 
  tree * node=new tree().
  node->getValueFromStream(mergedstream);
 
  if (size>1)
  {
    int leftsize= (size-1)/2;
    int rightsize= size-1 - leftsize;
 
    node->setLeft(buildtree(mergedstream, leftsize));
    node->setRight(buildtree(mergedstream, rightsize));
  }
}
« Last Edit: May 24th, 2007, 8:24am by towr » IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
A
Full Member
***



Perder todas as esperanças é liberdade!

   


Gender: male
Posts: 236
Re: Binary search tree merging  
« Reply #13 on: May 24th, 2007, 9:04am »
Quote Quote Modify Modify

on May 24th, 2007, 8:20am, towr wrote:

You use recursion, and treat the elements from the merging as an incoming stream.
Since you know the number of elements (which was given as an assumption), you know how many need to go to the first subtree and how many in the next subtree. And recursively you know it for each subtree.
 
So, I suppose
Code:

 
buildtree(stream &mergedstream, int size)
{
  if (!size || !mergedstream)
    return 0;
 
  tree * node=new tree().
  node->getValueFromStream(mergedstream);
 
  if (size>1)
  {
    int leftsize= (size-1)/2;
    int rightsize= size-1 - leftsize;
 
    node->setLeft(buildtree(mergedstream, leftsize));
    node->setRight(buildtree(mergedstream, rightsize));
  }
}

 
 
Ok , Just to make Sure i have understood it  correctly ....
 
Here  
Code:

....
....
tree * node=new tree().
node->getValueFromStream(mergedstream);
....
....

 
getValueFromStream()  is Nothing But the The Merged Input Treated as Preoder Traversal of the Merged Tree , Right  ? .
 
Hmmmm Thats what above 2 posts says , Hmmm Now i have understood it correctly  Grin  
 
 
Thanks Towr
IP Logged

What Doesn't Kill Me Will Only Make Me Stronger
towr
wu::riddles Moderator
Uberpuzzler
*****



Some people are average, some are just mean.

   


Gender: male
Posts: 13730
Re: Binary search tree merging  
« Reply #14 on: May 24th, 2007, 12:53pm »
Quote Quote Modify Modify

on May 24th, 2007, 9:04am, R0B1N wrote:
Ok , Just to make Sure i have understood it  correctly ....
 
Here  
Code:

....
....
tree * node=new tree().
node->getValueFromStream(mergedstream);
....
....

 
getValueFromStream()  is Nothing But the The Merged Input Treated as Preoder Traversal of the Merged Tree , Right  ?
getValueFromStream() takes the next piece of data from "mergedstream" and puts it in the node. The "mergedstream" can be seen as the inorder traversal of the merged tree (or more accurately, it's the merger of the two inorder traversals of the input trees).
From this you can surmise that I have in fact made a mistake in my pseudocode.  
 
It should be:
Code:
buildtree(stream &mergedstream, int size)
{
  if (!size || !mergedstream)
    return 0;
 
  tree * node=new tree().
  if (size=1)
    node->getValueFromStream(mergedstream);  
 else
  {
    int leftsize= (size-1)/2;
    int rightsize= size-1 - leftsize;
 
    node->setLeft(buildtree(mergedstream, leftsize));
    node->getValueFromStream(mergedstream);
    node->setRight(buildtree(mergedstream, rightsize));
  }
}

« Last Edit: May 24th, 2007, 12:54pm by towr » IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
arunrambo2000
Newbie
*





   


Posts: 21
Re: Binary search tree merging  
« Reply #15 on: May 28th, 2007, 12:09pm »
Quote Quote Modify Modify

I think for merging using an extra array may be costly... so i think we can go inorder traversal simultaneously and put the elements in sorted order in an array of O(m+n) in O(m+n)..
 
Then we can rebuild the new BST from the array as Knuther specified in a recursive manner in O(m+n)  
 
« Last Edit: May 28th, 2007, 12:14pm by arunrambo2000 » IP Logged
A
Full Member
***



Perder todas as esperanças é liberdade!

   


Gender: male
Posts: 236
Re: Binary search tree merging  
« Reply #16 on: May 29th, 2007, 12:12am »
Quote Quote Modify Modify

on May 28th, 2007, 12:09pm, arunrambo2000 wrote:
I think for merging using an extra array may be costly... so i think we can go inorder traversal simultaneously and put the elements in sorted order in an array of O(m+n) in O(m+n)..

 
Thats what the discussion is about and in the above method we not even using extra O(m+n) space for merged array  
 Roll Eyes
IP Logged

What Doesn't Kill Me Will Only Make Me Stronger
u_think_u_succeed
Newbie
*





   


Gender: male
Posts: 31
Re: Binary search tree merging  
« Reply #17 on: Jul 19th, 2007, 12:14am »
Quote Quote Modify Modify

Towr ..
 
Don't you think your "on the fly" build of the "merged" bst, when the number of elements is known a priori, takes O(n lgn) time in the worst case, as we are inserying each element, each of which may take time O(lg n) time ..
 
NOTE :: Here n = total number of nodes from the two original treees
IP Logged
u_think_u_succeed
Newbie
*





   


Gender: male
Posts: 31
Re: Binary search tree merging  
« Reply #18 on: Jul 19th, 2007, 12:35am »
Quote Quote Modify Modify

Moreover, I also find it hard to think that getting a sorted merged entity of two trees (without using O(n) and O(m) array space) can be done PRACTICALLY. Assuming that the nodes do not contain a parent pointer, we will have to implement this strategy using iterative versions, using explicit stacks. That might itself lend to using O(n+m) space, (albeit it will be called extra stack space, not extra array space  Shocked )
 
What do you think ..?
IP Logged
towr
wu::riddles Moderator
Uberpuzzler
*****



Some people are average, some are just mean.

   


Gender: male
Posts: 13730
Re: Binary search tree merging  
« Reply #19 on: Jul 19th, 2007, 1:18am »
Quote Quote Modify Modify

on Jul 19th, 2007, 12:14am, u_think_u_succeed wrote:
Towr ..
 
Don't you think your "on the fly" build of the "merged" bst, when the number of elements is known a priori, takes O(n lgn) time in the worst case, as we are inserting each element, each of which may take time O(lg n) time ..
No, the input is already sorted, so each element can be put in place in O(1) time.
The same as if you were merging two sorted array into a sorted array. Making a sorted array from two unsorted ones would take O(n log n), but given they're sorted it's O(n).  
And this problem is equivalent to that. (It's easy to turn a bst into an array in O(n), and vice versa in the same time)
IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
towr
wu::riddles Moderator
Uberpuzzler
*****



Some people are average, some are just mean.

   


Gender: male
Posts: 13730
Re: Binary search tree merging  
« Reply #20 on: Jul 19th, 2007, 1:28am »
Quote Quote Modify Modify

on Jul 19th, 2007, 12:35am, u_think_u_succeed wrote:
Moreover, I also find it hard to think that getting a sorted merged entity of two trees (without using O(n) and O(m) array space) can be done PRACTICALLY.
There is an algorithm given; although some elements of it need to be implemented. It's certainly easier to use intermediate arrays, but it by no means necessary.
 
Quote:
Assuming that the nodes do not contain a parent pointer, we will have to implement this strategy using iterative versions, using explicit stacks.
Using the function stack might suffice. And you can manipulate the content of the tree in such a way that you only need a constant number of extra pointers (but that's hell in a handbasket).
 
Quote:
That might itself lend to using O(n+m) space, (albeit it will be called extra stack space, not extra array space  Shocked )
The maximum number of parents a node in a (reasonably balanced) tree would have is log(n), so the total extra space would be  O(log(n)+log(m)).
IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
mad
Junior Member
**





   


Posts: 118
Re: Binary search tree merging  
« Reply #21 on: Mar 9th, 2008, 10:32pm »
Quote Quote Modify Modify

on Jul 19th, 2007, 1:18am, towr wrote:

No, the input is already sorted, so each element can be put in place in O(1) time.
The same as if you were merging two sorted array into a sorted array. Making a sorted array from two unsorted ones would take O(n log n), but given they're sorted it's O(n).  
And this problem is equivalent to that. (It's easy to turn a bst into an array in O(n), and vice versa in the same time)

 
Could you please tell how to build a bst from a sorted array in O(n)? Is it by taking middle element as root, and taking middlde of the left side as its left subtree root and so on?
IP Logged
towr
wu::riddles Moderator
Uberpuzzler
*****



Some people are average, some are just mean.

   


Gender: male
Posts: 13730
Re: Binary search tree merging  
« Reply #22 on: Mar 10th, 2008, 2:05am »
Quote Quote Modify Modify

on Mar 9th, 2008, 10:32pm, mad wrote:
Is it by taking middle element as root, and taking middlde of the left side as its left subtree root and so on?
Yes.
IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
m_aakash
Junior Member
**





   


Posts: 96
Re: Binary search tree merging  
« Reply #23 on: Mar 10th, 2008, 2:24am »
Quote Quote Modify Modify

on Dec 9th, 2004, 1:04am, knuther wrote:
Got this question recently in an interview.....
 
There are two unbalanced binary search trees say T1 and T2. Find an efficient algorithm to merge these two trees into a (Height) Balanced Binary search tree T3.
 
Brute force algorithm would require O(n logm)+Time for balancing with n being number of nodes in T1 and m being number of nodes in T2. or O(m log n) + Balancing time.
 
 
can we  optimize on this using extra space?

 
a) Convert both the bst into sorted doubly linked lists in O(n+m) time.
b)merge the two double linked lists into one and also maintain the count of total elements in O(n+m) time.
c)convert the sorted doubly linked list into height balacned tree in O(n+m) time.
 
It takes O(n+m) time and O(1) space.
 
« Last Edit: Mar 10th, 2008, 2:26am by m_aakash » IP Logged
m_aakash
Junior Member
**





   


Posts: 96
Re: Binary search tree merging  
« Reply #24 on: Mar 10th, 2008, 2:30am »
Quote Quote Modify Modify

on Mar 9th, 2008, 10:32pm, mad wrote:

 
Could you please tell how to build a bst from a sorted array in O(n)? Is it by taking middle element as root, and taking middlde of the left side as its left subtree root and so on?

 
Taking middle and building left  and right subtrees is one approach.
Other way is that since u know the number of elements in the array, build the tree recursively with the count and while coming from bottom of the recursion u can fill the tree node values with given array elements in sequence as well.
IP Logged
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print

« Previous topic | Next topic »

Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board