Author |
Topic: common elements of 2 bst (Read 2094 times) |
|
witee
Newbie
Posts: 48
|
 |
common elements of 2 bst
« on: Mar 24th, 2010, 4:06pm » |
 Quote  Modify
|
Find the common elements of 2 bst with max efficiency?
sorry if it is discussed previously but i couldn't find it.
|
|
 IP Logged |
|
|
|
kaka
Newbie
Gender: 
Posts: 24
|
|
Re: common elements of 2 bst
« Reply #1 on: Mar 24th, 2010, 10:28pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: common elements of 2 bst
« Reply #2 on: Mar 25th, 2010, 2:07am » |
Quote Modify
|
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.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
witee
Newbie
Posts: 48
|
|
Re: common elements of 2 bst
« Reply #3 on: Mar 25th, 2010, 7:38am » |
Quote Modify
|
how to do inorder traversal of both tree in one program ?? can u give the pseudocode/code of it??
|
|
IP Logged |
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: common elements of 2 bst
« Reply #4 on: Mar 25th, 2010, 7:58am » |
Quote Modify
|
on Mar 25th, 2010, 2:07am, towr wrote:| You can just do a simultaneous in-order tree traversal. |
|
You mean pre-order, yes?
--SMQ
|
|
IP Logged |
--SMQ
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: common elements of 2 bst
« Reply #5 on: Mar 25th, 2010, 8:15am » |
Quote Modify
|
on Mar 25th, 2010, 7:38am, 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);
} |
|
|
| « Last Edit: Mar 25th, 2010, 8:18am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: common elements of 2 bst
« Reply #6 on: Mar 25th, 2010, 8:16am » |
Quote Modify
|
on Mar 25th, 2010, 7:58am, SMQ 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.
|
| « Last Edit: Mar 25th, 2010, 8:18am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: common elements of 2 bst
« Reply #7 on: Mar 25th, 2010, 8:37am » |
Quote Modify
|
on Mar 25th, 2010, 8:16am, 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
|
|
IP Logged |
--SMQ
|
|
|
KWillets
Junior Member
Posts: 84
|
|
Re: common elements of 2 bst
« Reply #8 on: Mar 25th, 2010, 3:08pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: common elements of 2 bst
« Reply #9 on: Mar 25th, 2010, 3:46pm » |
Quote Modify
|
on Mar 25th, 2010, 3:08pm, 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.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: common elements of 2 bst
« Reply #10 on: Mar 26th, 2010, 7:06am » |
Quote Modify
|
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.
|
| « Last Edit: Mar 31st, 2010, 8:51am by Grimbal » |
IP Logged |
|
|
|
kaka
Newbie
Gender:
Posts: 24
|
|
Re: common elements of 2 bst
« Reply #11 on: Mar 26th, 2010, 12:59pm » |
Quote Modify
|
great algo grimbal. looks like its O(n) worst case , but the average and best case are of O(logn).
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: common elements of 2 bst
« Reply #12 on: Mar 29th, 2010, 2:15am » |
Quote Modify
|
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).
|
| « Last Edit: Mar 29th, 2010, 2:18am by Grimbal » |
IP Logged |
|
|
|
diptendubhowmick
Newbie
Posts: 11
|
|
Re: common elements of 2 bst
« Reply #13 on: Mar 31st, 2010, 3:52am » |
Quote Modify
|
For each element in one tree you need O(logn). So total time complexity is O(nlogn). Right?
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: common elements of 2 bst
« Reply #14 on: Mar 31st, 2010, 4:18am » |
Quote Modify
|
on Mar 31st, 2010, 3:52am, 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).
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
srikanth.iiita
Newbie
Posts: 33
|
|
Re: common elements of 2 bst
« Reply #15 on: Mar 31st, 2010, 8:20am » |
Quote Modify
|
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...
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: common elements of 2 bst
« Reply #16 on: Mar 31st, 2010, 8:30am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print