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
@Nikhil : For that size of subtrees at all nodes needs to be maintained. And
in that case this is a trivial problem.
@Sathaiah : See my solution :)
--
Rohit Saraf
Second Year Undergraduate,
Dept. of Computer Science and Engineering
IIT Bombay
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
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)
{