Sunday, September 11, 2011

Find nth largest value in a BST

Simplest solution is to do a reverse in order search and maintain a global counter.
ReverseInOrder(Tree T, n)
1. if (T->right != null ) ReverseInOrder(T->right)
2. if (count==n) return T. Else count++
3. if (T->left != null ) ReverseInOrder(T->left)

1 comment:

  1. Hi there
    I was just going through your this post and had a small doubt.
    Shouldn't we do a stack based iterative traversal to get the correct value in this code ? This recursive may give wrong result as it will start counting after the rightmost element has been found. This element won't be the nth largest in BST.
    What do you think ? Nice blog, anyways!

    ReplyDelete