If you maintain the size of the subtree rooted at the nodes, then it will become easier. I guess you can see how.
Else, 1) Use any algo to count the number of nodes in the BST.Let it be n. 2) Use morris inorder(no recursion/no stacks-all constraint met ) to traverse the tree. For each node visited increment the counter. a) If n is even then return avg(n/2,n/2+1)(counter == n/2) b) If n is odd return when counter == (n+1)/2(1-based indexing) You might want to read this up. : http://www.scss.tcd.ie/disciplines/software_systems/fmg/fmg_web/IFMSIG/winter2000/HughGibbonsSlides.pdf -------------------------------------------------- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 -- 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.
