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 <[email protected]>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 <[email protected]> wrote: > >> 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]<algogeeks%[email protected]> >> . >> 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 [email protected]. > To unsubscribe from this group, send email to > [email protected]<algogeeks%[email protected]> > . > 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 [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.
