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)
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)
Hi there
ReplyDeleteI 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!