# 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.

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.

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).

(1 votes, average: 5.00 out of 5)