wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> common elements of 2 bst 
        
(Message started by: witee on Mar 24^th, 2010, 4:06pm)

Title: common elements of 2 bst
Post by witee on Mar 24^th, 2010, 4:06pm

Find the common elements of 2 bst with max efficiency?:P
sorry if it is discussed previously but i couldn't find it.

Title: Re: common elements of 2 bst
Post by kaka189 on Mar 24^th, 2010, 10:28pm

Take each element from one and search for it in another. mlogn .If we know sizes then make m as the least one.
If we are allowed to change the nodes or use extra space, then convert them into linked list (need not be dll, O(n) time) and search for common elements in two sorted lists in O(n) time.

Title: Re: common elements of 2 bst
Post by towr on Mar 25^th, 2010, 2:07am

You can just do a simultaneous in-order tree traversal. It saves you the trouble of having to convert the trees to linked lists, or arrays, and it changes nothing about the basic algorithm. Just go to the next element in on tree if it's smaller than the current element in the other tree; if they're the same store it, and go to the next in both trees.

Title: Re: common elements of 2 bst
Post by witee on Mar 25^th, 2010, 7:38am

how to do inorder traversal of both tree in one program ?? can u give the pseudocode/code of it??

Title: Re: common elements of 2 bst
Post by SMQ on Mar 25^th, 2010, 7:58am

on 03/25/10 at 02:07:53, towr wrote:

You can just do a simultaneous in-order tree traversal.

You mean pre-order, yes?

--SMQ

Title: Re: common elements of 2 bst
Post by towr on Mar 25^th, 2010, 8:15am

on 03/25/10 at 07:38:09, witee wrote:

how to do inorder traversal of both tree in one program ?? can u give the pseudocode/code of it??

You have to keep stacks for both trees (unless they have something like parent pointers or next pointers).

I think/hope the following two functions should do it. (But honestly, it's one of those "I know it's possible, but I'll avoid it if I can" kind of things)

Code:

void init_stack(stack, root)
{
stack.clear();
while(root)
{
stack.push(root);
root=root->left;
}
}

int next_val(stack)
{
currentnode = stack.pop();

if (root = currentnode->right)
{
while(root)
{
stack.push(root);
root=root->left;
}
return currentnode->val();
}

Using those two functions, we should be able to just run through both trees with something like:

Code:

init_stack(stack1, tree1);
init_stack(stack2, tree2);

t1=next_val(stack1);
t2=next_val(stack2);
while( ! stack1.isempty() && ! stack2.isempty() )
{
if(t1 == t2)
{
print t1;
t1 = next_val(stack1);
t2 = next_val(stack2);
}
else if (t1 < t2)
t1 = next_val(stack1);
else
t2 = next_val(stack2);
}

Title: Re: common elements of 2 bst
Post by towr on Mar 25^th, 2010, 8:16am

on 03/25/10 at 07:58:16, SMQ wrote:

You mean pre-order, yes?

Err, no? That doesn't sound like a good idea to me.
We want to encounter all elements in increasing order. If we use preorder that'll screw everything up.

Title: Re: common elements of 2 bst
Post by SMQ on Mar 25^th, 2010, 8:37am

on 03/25/10 at 08:16:45, towr wrote:

Err, no? That doesn't sound like a good idea to me.
We want to encounter all elements in increasing order. If we use preorder that'll screw everything up.

:-[ Um, yeah. I just has the terms backwards in my head this morning for some reason...

--SMQ

Title: Re: common elements of 2 bst
Post by KWillets on Mar 25^th, 2010, 3:08pm

Merging sorted lists is o(n) only if both lists are equal in size. Knuth has some references on unequal-sized lists, but all I remember is that if one list is k times bigger, we step through the larger array in steps of k at a time and binary search to find each match, instead of scanning the entire array. If the smaller array is size m, this yields o(m log k) comparisons instead of mk (IIRC).

A similar thing might work with balanced trees if we only inorder-traverse the larger tree to the depth of the smaller tree, and search subtrees below that depth only as needed.

Title: Re: common elements of 2 bst
Post by towr on Mar 25^th, 2010, 3:46pm

on 03/25/10 at 15:08:05, KWillets wrote:

A similar thing might work with balanced trees if we only inorder-traverse the larger tree to the depth of the smaller tree, and search subtrees below that depth only as needed.

I don't think it would be a good idea to simply limit the inorder search in the large tree to a certain depth. We might decide much earlier that we can skip parts. And that's even true if the trees are the same size. There must be some way to use that extra information.
Maybe a way to apply divide and conquer; splitting both trees, till you're left with one element to search in a small tree. Well, it's late, guess I'll have to sleep on it.

Title: Re: common elements of 2 bst
Post by Grimbal on Mar 26^th, 2010, 7:06am

I don't know how bad the run time can be but you can do:

void common(node a, node b)
{
if( a==null || b==null ) return;
// left side of a
node n = b;
while( n!=null && n.val>=a.val ) n = n.left;
common(a.left, n);
// root of a
if( a.val == b.val){
// common element
print(a.val);
}
// right side of a
n = b;
while( n!=null && n.val<=a.val ) n = n.right;
common(a.right, n);
}

PS: this code doesn't work. See below.

Title: Re: common elements of 2 bst
Post by kaka189 on Mar 26^th, 2010, 12:59pm

great algo grimbal. looks like its O(n) worst case , but the average and best case are of O(logn).

Title: Re: common elements of 2 bst
Post by Grimbal on Mar 29^th, 2010, 2:15am

~~I doubt it can be O(log n) since I am testing each value of a and each value of b at least once.~~

Oops, you are right. It can be O(log n).

Title: Re: common elements of 2 bst
Post by diptendubhowmick on Mar 31^st, 2010, 3:52am

For each element in one tree you need O(logn). So total time complexity is O(nlogn). Right?

Title: Re: common elements of 2 bst
Post by towr on Mar 31^st, 2010, 4:18am

on 03/31/10 at 03:52:18, diptendubhowmick wrote:

For each element in one tree you need O(logn). So total time complexity is O(nlogn). Right?

No, because you don't need to start a search from the root for each element. O(n) is easily achieved (just look at the previous solutions).

Title: Re: common elements of 2 bst
Post by srikanth.iiita on Mar 31^st, 2010, 8:20am

i went through Grimbal's code....

two trees
are
........7....
....5.......9
..4.............11
and
.......10......
.....7.. ...12..
...5............13

but this is not printing 7 as common element....

Correct me if Iam wrong...

Title: Re: common elements of 2 bst
Post by Grimbal on Mar 31^st, 2010, 8:30am

Er... well... Have you tried to reboot? :-[

OK, I didn't even try to compile it before posting it. That might explain something. And now that you mention it, I can see what is wrong. It needs some more work.

Thanks for pointing that out.