Do an iterative inorder traversal and stop at k ? Best, Prakhar Jain http://web.iiit.ac.in/~prakharjain/
On Thu, Dec 10, 2009 at 7:38 AM, Rohit Saraf <[email protected]>wrote: > You can maintain the size. or it can be computed in at worst linear time. > In first method, the only difference is that it will make the kth smallest > element the root of the tree. When in 2nd method it goes to left, in first > method it will also go to left but rotate the tree right. > > Rohit Saraf > Sophomore > Computer Science and Engineering > IIT Bombay > > > On Wed, Dec 9, 2009 at 9:45 PM, Vikram Sridar > <[email protected]>wrote: > >> read augmenting data structures (chapter 14 i think) in Introduction in >> Algorithms by Corman.. if an extra attribute is added to each of the nodes >> storing the number of elements in the sub tree rooted at the node, this can >> be done easily.. the extra is neither global or static(as it is created n >> destroyed with each node).. >> >> -- >> 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]<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.
