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.