Solution: Kth Smallest Element in a BST

Statement#

Given the root node of a binary search tree and an integer value k, return the $k^{th}$ smallest value in the tree.

Constraints:

• The number of nodes in the tree is $n$.
• $1 \leq k \leq n \leq 10^4$
• $0 \leq$ Node.data $\leq 10^4$

Solution#

For this solution, we will recursively perform the inorder traversal(left subtree, root, right subtree) on the binary search tree. We will use the inorder traversal to get elements in sorted order.

While performing the inorder traversal on the tree, decrement k by $1$, indicating the number of smaller elements that still need to be found. After decrementing k, we check whether the value of k has reached $0$. If it is $0$, we return the current node, indicating the node having the $k^{th}$ smallest element. If not, continue the traversal.

This approach ensures that we traverse the tree in a depth-first manner while appropriately updating k and effectively finding the $k^{th}$ smallest element.

Now, let’s look at the following illustration to get a better understanding of the solution:

Let’s look at the code for this solution below:

Time complexity#

The time complexity of this solution is $O(n)$, where $n$ represents the number of nodes in the binary tree.

Space complexity#

The space complexity of this solution is $O(n)$. This is because our recursive algorithm uses space on the call stack.