Sorry, but.. why don't you.. a) compute the height of each subtree. Recusrively, takes O(n). b) start from the root. if its left subtree is bigger than the right one, than solution is on the left, since a symmetric traversal would put the root after more than half the elements, sorting them. so, recurse to the left, o.w. adjust k and recurse to the right.
-- 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.