would it be possible to come with the abstract solution with the following
idea.
1. Use the inorder traversal, (we know this it prints elements in ascending
order)
2. Use the same inorder traversal (inorder_rev) with the left, right
change,( this will print in descending order)
3. Can we use this inorder and inorder_rev to find the median ?
If we use explicit stack to do this traversal, I think we can get the
solution, but it needs memory.
Thanks,
Sathaiah
On Sat, May 15, 2010 at 10:52 AM, Nikhil Agarwal
<nikhil.bhoja...@gmail.com>wrote:
>
> We can try rotation too.
>
> 1.We iterate rotating of the left/right sub-tree having greater number of
> nodes.
> 2. if number of keys are :-
> ODD-> Equal number of nodes exist on both left and rt subtree of root .Key
> at root is the median of the BST..
> EVEN->left subtree should have 1 less node than right.Both root node and a
> node just below on the rt. sub tree will be the median.
>
>
> On Sat, May 15, 2010 at 2:31 AM, W Karas <wka...@yahoo.com> wrote:
>
>> On May 14, 3:32 am, divya <sweetdivya....@gmail.com> 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 algoge...@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com>
>> .
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>>
>
>
> --
> Thanks & Regards
> Nikhil Agarwal
> Senior Undergraduate
> Computer Science & Engineering,
> National Institute Of Technology, Durgapur,India
> http://tech-nikk.blogspot.com
>
>
>
> --
> 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<algogeeks%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.
