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. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.