Given a binary search tree, how do we find a k^{th} smallest or k^{th} largest element?

For example, given the following binary search tree.

Third largest element is 6

Second smallest element is 2

Fifth largest element is 5 and so on…
**Solution: **

We can solve this problem by modifying the the in-order traversal method of a binary tree. In addition to the root node, we can pass two more parameters one is K, and current count of the nodes visited as a reference parameter. When the current count reaches K we found the k^{th} order element.

To find out the k^{th} smallest element, we need to visit left sub-tree, then root and then the right sub-tree as usual. To find the k^{th} largest element we need to do reverse in-order traversal i.e First visit right sub-tree, then root and then the left sub-tree.

Here is the C++ implementation. This includes the recursive and iteration versions of finding k^{th} smallest and k^{th} largest elements. The iterative version is simply the manual implementation of a recursion using a stack.