On May 14, 3:32 am, divya <[email protected]> wrote:
> please suggest an efficient algo to find the median of a bst
A recursive solution:
unsigned count(node_handle_t base)
{ return(base == null ? 0 : count(left(base)) + 1 +
count(right(base))); }
val_t max(node_handle_t base)
{ return(right(base) == null ? val(base) : max(right(base))); }
val_t min(node_handle_t base)
{ return(left(base) == null ? val(base) : min(left(base))); }
val_t median_help(
node_handle_t base,
unsigned low_count,
unsigned high_count)
{
unsigned left_count, right_count;
left_count = count(left(base));
right_count = count(right(base));
low_count += left_count;
high_count += right_count;
if (low_count == high_count)
return(val(base));
if (low_count == (high_count + 1))
return((val(base) + max(left(base))) / 2);
if (high_count == (low_count + 1))
return((val(base) + min(right(base))) / 2);
if (low_count > high_count)
return(median_help(left(base), low_count - left_count,
high_count + 1));
/* low_count < high_count */
return(median_help(right(base), low_count + 1, high_count -
right_count));
}
val_t median(node_handle_t root)
{ return(median_help(root, 0, 0)); }
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
