If the tree is balanced, and if you store the number of nodes in the subtree rooted at each node in the tree, it can be achieved in O(log n). It is tree to verify that this extra information can be maintained with all insert, del operations at no extra cost.
On Feb 28, 11:36 am, "Lego Haryanto" <[EMAIL PROTECTED]> wrote: > If the BST is balance, you could do it better in O(lg n). I believe > some setup should be involved, such as storing how many nodes in a > subtree. > > Best, > -Lego > > On 2/28/08, Dave <[EMAIL PROTECTED]> wrote: > > > > > Do an inordertraversal. Stop when you get to the kth node. O(k). > > > Dave > > > On Feb 28, 12:30 am, yash <[EMAIL PROTECTED]> wrote: > > > Binary search Tree was given. Find kth smallest element. and also find > > > complexity. > > -- > Fear of the LORD is the beginning of knowledge (Proverbs 1:7) --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
