K’th Smallest Element in BST

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

1. Initialize ‘count’ to zero, ‘element’ = INT_MIN, and ‘current’ as ‘root’
2. While ‘current’ is not equal to NULL
3. 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’
    
4. Else
   1. Find the rightmost node in the current left subtree OR node whose right child is not equal to the current
       
   2. If right child == NULL
      - Link it to the inorder successor as prev->right = current
      - Go to the left subtree, i.e., ‘current’ = ‘current->left’
       
   3. 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’
       
5. 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);

}

You can also try this code with Online C++ Compiler

Run Code

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.

Check out this problem - Next Smaller Element

Frequently Asked Questions

What is Morris traversal?

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

• Balanced Binary Search Trees 
• Check if two BSTs contain the same set of elements or not
• Check for identical BSTs without building the trees
• Check if an array represents inorder of a BST
   

Refer to our guided paths on Coding Ninjas Studio to learn more about DSA, Competitive Programming, JavaScript, System Design, etc. And also, enroll in our courses and refer to the mock test and problems available. Have a look at the interview experiences and interview bundle for placement preparations. Nevertheless, you may consider our paid courses to give your career an edge over others!

Happy Coding