Find k’th smallest node in a Binary Search Tree (BST)

Given a Binary Search Tree (BST) and a positive number k, find the K-th smallest node in it.

For example, the 4th smallest node in the following BST is 15 and 6’th smallest is 20. 8’th smallest node does not exist.

kth-smallest-largest-element

 
The idea is to traverse the BST in inorder fashion since inorder traversal visits the nodes of a BST in the sorted order. We maintain a counter along with recursion that keeps track of the visited nodes and when that counter reaches k, we return that node.

The algorithm can be implemented as follows. The code is optimized to visit the right subtree only when the k’th smallest is not found in the left subtree.

 

Download   Run Code

Output:

4’th smallest elment is 15

 
The time complexity of the above solution is O(n) and requires O(n) implicit space for the recursive call stack.

 
Exercise:

1. Modify the solution to find the k’th largest node in a BST (Check solution here).

2. Modify the solution to print the first k smallest nodes in a BST (Check solution here).

 
Thanks for reading.

Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 


Leave a Reply

avatar
  Subscribe  
Notify of