Re: [algogeeks] Median of BST
@Kaushik,
I think you can do using inorder successor also, using this successor you
can think of BST as Sorted List.
What do you say ?
Thanks,
Sathaiah
On Wed, May 19, 2010 at 11:11 AM, kaushik sur kaushik@gmail.com wrote:
@Dhilip
Is it tested ? I doubt your code won't work ?
@Rohit
Can we anyways modify Morris Inorder Traversal process? We can have two
pointers slow(increments once) and fast(increments twice), so that if fast
reaches end or fast-next is end, we can have the median @ slow ?
Correct me If I am wrong.
Thanks and Regards
Kaushik
On Tue, May 18, 2010 at 4:05 PM, dhilip dhilip.i...@gmail.com wrote:
1)do inorder and reverse inorder traversal
2)They will meet at one point or they will cross each other
3)That point is the median
4)Code for the same.
while(true)
{
//inorder traversal
while(count1=count2 flag1)
{
if(root)
{
push(root);
root=root-lptr;
}
else
{
if(!isEmpty(stack1))
t=pop();
else
flag1=false;
var1=t-data;
count1++;
root=t-rptr;
}
if(count1==count2)
{
if(var1=var2)
return var2;
}
}
//reverse inorder
while(count2=count1 flag2)
{
if(root1)
{
push(root1);
root1=root1-rptr;
}
else
{
if(!isEmpty(stack2))
t1=pop();
else
flag2=false;
var2=t1-data;
count2++;
root1=t1-lptr;
}
if(count1==count2)
{
if(var1=var2)
return var2;
}
}
}
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Median of BST
@donthulla plzz write code 4 ur logic -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Median of BST
@Dhilip
Is it tested ? I doubt your code won't work ?
@Rohit
Can we anyways modify Morris Inorder Traversal process? We can have two
pointers slow(increments once) and fast(increments twice), so that if fast
reaches end or fast-next is end, we can have the median @ slow ?
Correct me If I am wrong.
Thanks and Regards
Kaushik
On Tue, May 18, 2010 at 4:05 PM, dhilip dhilip.i...@gmail.com wrote:
1)do inorder and reverse inorder traversal
2)They will meet at one point or they will cross each other
3)That point is the median
4)Code for the same.
while(true)
{
//inorder traversal
while(count1=count2 flag1)
{
if(root)
{
push(root);
root=root-lptr;
}
else
{
if(!isEmpty(stack1))
t=pop();
else
flag1=false;
var1=t-data;
count1++;
root=t-rptr;
}
if(count1==count2)
{
if(var1=var2)
return var2;
}
}
//reverse inorder
while(count2=count1 flag2)
{
if(root1)
{
push(root1);
root1=root1-rptr;
}
else
{
if(!isEmpty(stack2))
t1=pop();
else
flag2=false;
var2=t1-data;
count2++;
root1=t1-lptr;
}
if(count1==count2)
{
if(var1=var2)
return var2;
}
}
}
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
