A (BST) binary search tree is a tree in which all nodes left to the root node have values less than the root node, and all nodes right to the root node have values greater than the root node. The other difference is all of the subtrees in the binary search tree are themselves a binary search tree.

This blog will discuss a simple DSA problem: K’th smallest element in BST.

Problem Statement 🧾

The problem "K’th smallest element in BST," states that you are given a BST(Binary Search Tree) and a positive integer K. Our task is to print the K’th smallest element in the given BST.

Let's have an example to make the problem statement clear.

Example

Input: The value of K =3

Output: K’th smallest element is: 5

Approach

For K’th smallest element in BST, we will use Morris Traversal in which you have to add links to the in-order successor, and later you can find the kth smallest element using these links.

Algorithm

Initialize ‘count’ to zero, ‘element’ = INT_MIN, and ‘current’ as ‘root’

While ‘current’ is not equal to NULL

If the ‘current’ node does not have a left child - Increment the value of ‘count’ - Check if ‘count’ == ‘k’, set ‘element’ = ‘current->data’ - Go to the right subtree, i.e., ‘current’ = ‘current->right’

Else

Find the rightmost node in the current left subtree OR node whose right child is not equal to the current

If right child == NULL - Link it to the inorder successor as prev->right = current - Go to the left subtree, i.e., ‘current’ = ‘current->left’

Else - Set ‘prev->right’ == NULL - Increment the value of ‘count’ - Check if ‘count’ == ‘k’, set ‘element’ = ‘current->data’ - Go to the right subtree, i.e., ‘current’ = ‘current->right’

Return the value of the ‘element’

Example

Let's now discuss working through an example, and then we will code it:

As current = root = 9. So, current != NULL, start iteration 1

Iteration 1

Current->left = 5 != NULL

Move to else condition

Prev = current->left = 5, now find the rightmost node in the current left subtree AND node whose right child is not equal to the current

After loop, prev->right = NULL

So link it to inorder successor i.e prev->right = current = 9 (8->9)

Assign current = current->left = 5 != NULL. Move to the next iteration

Iteration 2

Current->left = 2 != NULL

Move to the else condition

Prev = current->left = 2

After loop, prev->right == NULL

So link it to inorder successor i.e prev->right = current = 5 (2->5)

Assign current = current->left = 2 != NULL. Move to the next iteration

Iteration 3

Current->left == NULL

Increment count, so now count = 1

Check count == k (1 != 3) so false

Current = current->right = 5 != NULL. Move to the next iteration

Iteration 4

Current = 5 != NULL

current->left = 2 != NULL

Move to condition else

Prev =current->left = 2

As here prev->right == current = 5. So end while loop.

prev->right = 5 != NULL. Move to the else block.

Set prev->right = NULL. (2 -> NULL)

Increment count, so now count = 2

Check count == k (2 != 3) so false

Current = current->right = 8 != NULL. Move to the next iteration

Iteration 5

Current = 8 != NULL.

current->left (8->left) = NULL.

Increment count, so now count = 3

Set value of element = current->data = 8

Current = current->right (8->right) = NULL. Stop iteration

Return the element's value to print K’th smallest element in BST, i.e., 8. Let's implement the solution to the problem.

Implementation in C++

// C++ program to find K’th smallest element in BST
#include<bits/stdc++.h>
using namespace std;
struct Node
{
int data;
Node *left;
Node *right;
};
int KSmallest(Node *root, int k)
{
// Count until get the kth smallest number
int count = 0;
// To store kth smallest element
int ksmall = INT_MIN;
// Node to store the current node
Node *curr = root;
while (curr != NULL)
{
// If the left child is null, increment count.
if (curr->left == NULL)
{
count++;
// Check if count becomes equal to K
if (count==k)
ksmall = curr->data;
// Set current to the right child
curr = curr->right;
}
else
{
// If the current is not null, add a link to inorder successor
Node *prev = curr->left;
while (prev->right != NULL && prev->right != curr)
prev = prev->right;
if (prev->right==NULL)
{
// link right to inorder sccessor
prev->right = curr;
curr = curr->left;
}
else
{
prev->right = NULL;
count++;
// Check if count becomes equal to K
if (count==k)
ksmall = curr->data;
// Check for the right subtree
curr = curr->right;
}
}
}
// Return Kth smallest element
return ksmall;
}
// Function to create newnode
Node *newNode(int item)
{
Node *temp = new Node;
temp->data = item;
temp->left = temp->right = NULL;
return temp;
}
// Function to insert nodes in the tree.
Node* insert(Node* node, int data)
{
// If the root node is empty, return a new node
if (node == NULL)
return newNode(data);
// If data is less than the root node, add it to the left subtree
if (data < node->data)
node->left = insert(node->left, data);
// If data is greater than the root node, add it to the right subtree
else if (data > node->data)
node->right = insert(node->right, data);
return node;
}
int main()
{
int n;
cout<<"Enter number of nodes : ";
cin>>n;
Node *root = NULL;
cout<<"Enter "<<n<<" nodes : ";
int x;
cin>>x;
root = insert(root, x);
for(int i=0;i<n-1;i++)
{
cin>>x;
insert(root, x);
}
int k;
cout<<"Enter a +ve integer K : ";
cin>>k;
cout<<"K’th smallest element is :"<<KSmallest(root, k);
}

Output

Time Complexity ⌛

The time complexity of the problem “K’th smallest element in BST” using the above approach is O(N), where N is the number of nodes of BST.

In morris traversal, each edge is traversed almost 3 times.

As the number of edges in the binary search tree is N-1.

So time taken to traverse N-1 edges 3 times = 3x(N-1).

In terms of Asymptotic notations time complexity = O(3x(N-1)) = O(N)

Space Complexity 🚀

The space complexity of the problem “K’th smallest element in BST” using the above approach is O(N) for storing N nodes of BST taken input by the user and O(1) auxiliary space.

We can traverse the tree without using recursion or stack by using Morris Traversal. Morris Traversal is based on the Threaded Binary Tree concept. We build links to Inorder successors and display the data using these links in this traversal, then at the end reverse the changes to restore the original tree.

What is a binary search tree?

A binary search tree is a binary tree in which all of the nodes left to the root node have values less than the root node, and all of the nodes right to the root node have values greater than the root node.

What is a Threaded Binary Tree?

A threaded binary tree is just like a normal binary tree, but they have a specialty in which all the nodes whose right child pointers are NULL point to their in-order successor, and all the nodes whose left child pointers are NULL point to their in-order predecessor.

Why is Binary Search Tree used?

It is beneficial in many scenarios where we have to compare the sorted data then it can be used.

What is the time complexity to find K’th smallest element in BST?

The time complexity to find K’th smallest element in BST is O(N), where N is the number of nodes in the binary search tree.

Conclusion

In this article, we have discussed a coding problem in which we have to find the K’th smallest element in BST. We have seen the question's solution, time, and space complexity(K’th smallest element in BST).

If you found this blog has helped you enhance your knowledge about the above question, and if you want to learn more, check out our articles