K-th smallest element in BST

Recursive Approach

In this approach, we will perform the standard inorder traversal, as the inorder traversal of a Binary Search Tree is an array sorted in ascending order.

There are two main steps in this approach:

1. Perform the in-order traversal on the BST.
2. The result of the Kth iteration will be our answer.

Algorithm

1. Perform standard inorder traversal (left subtree → root → right subtree)
2. Take K as an argument(by reference) in the recursive function call.
3. While inorder traversal
   1. First, go to the left subtree
   2. Coming back from the left subtree, reduce K by one every time
   3. Check if K is equal to 0; if yes, then that's our answer
   4. To reduce extra traversals, go to the right subtree only if K is greater than 0.

Implementation

// C++ program to find Kth smallest element in the BST using recursive in order traversal

#include<bits/stdc++.h>
using namespace std;


// A BST node
struct Node {
    int data;
    Node *left, *right;
    Node(int x)
    {
        data = x;
        left = right = NULL;
    }
};


// Recursive function to insert a key into BST
Node* insert(Node* root, int x)
{
    if (root == NULL)
        return new Node(x);
    if (x < root->data)
        root->left = insert(root->left, x);
    else if (x > root->data)
        root->right = insert(root->right, x);
    return root;
}


void inorder(Node* root, int& k, int& ans){
    if(root==NULL)return;
//  first traverse left subtree
    inorder(root->left,k,ans);
    
//  decrement value of k till 0 to find the Kth smallest element
    k--;
    
//  when k==0, we've reached the kth smallest element
    if(k==0){
        ans = root->data;
        return;
    }
    
//  no need to traverse after k<=0 because we've already found the answer
    if(k>0)
        inorder(root->right,k,ans);
}
int kthSmallest(Node* root, int k) {
    int ans = 0;
    inorder(root,k,ans);
    return ans;
}

int main()
{
    Node* root = NULL;
    vector<int> keys = { 5 , 2 , 1, 4 , 3 , 6 , 7 };


    for (int x : keys)
        root = insert(root, x);
    
    int k = 4;
    cout << kthSmallest(root, k);
    return 0;
}

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

Run Code

Output: 4

Output

For K=4
Inorder traversal for the constructed BST will be:

1 2 3 4 5 6 7

         ^

      4th element

Complexity analysis

Time Complexity: We return from the standard in-order traversal after the Kth call, so the time complexity is O(K+H), where H is the tree's height because we also go to the depth.

Space Complexity: O(height of tree) space complexity for recursion call stack.

Iterative Approach

The above recursive code can be converted into an iterative code with the help of a stack. This method speeds up the program as there is no need to build the entire inorder traversal, and we can stop after the kth element.

Algorithm

1. Perform iterative inorder traversal.
2. Run while loop till K>0 and push K smallest element in the stack.
3. When K=0, return the stack's top value, as it is the Kth smallest element.

Implementation

// C++ program to find Kth smallest element in the BST using recursive inorder traversal

#include<bits/stdc++.h>
using namespace std;

// A BST node
struct Node {
    int data;
    Node *left, *right;
    Node(int x)
    {
        data = x;
        left = right = NULL;
    }
};

// Recursive function to insert a key into BST
Node* insert(Node* root, int x)
{
    if (root == NULL)
        return new Node(x);
    if (x < root->data)
        root->left = insert(root->left, x);
    else if (x > root->data)
        root->right = insert(root->right, x);
    return root;
}

void inorder(Node* root, int& k, int& ans){
    if(root==NULL)return;
//  first traverse left subtree
    inorder(root->left,k,ans);
    
//  decrement value of k till 0 to find the Kth smallest element
    k--;
    
//  when k==0, we've reached the kth smallest element
    if(k==0){
        ans = root->data;
        return;
    }
    
//  no need to traverse after k<=0 because we've already found the answer
    if(k>0)
        inorder(root->right,k,ans);
}

void push_left_child(Node* root, stack<Node*>& st) {
//  push all left children till root is NULL
    while(root) {
        st.push(root);
        root = root->left;
    }
}
int kthSmallest(Node* root, int& k) {
    stack <Node*> st;
    push_left_child(root,st);
//  standard iterative inorder traversal
    while (k--){
        auto res = st.top();st.pop();
//      when K==0, we've reached the Kth smallest element, so we'll return the element
        if (k == 0) return res->data;
        push_left_child(res->right,st);
    }
    return -1;
}

int main()
{
    Node* root = NULL;
    vector<int> keys = { 5 , 2 , 1, 4 , 3 , 6 , 7 };


    for (int x : keys)
        root = insert(root, x);
    
    int k = 4;
    cout << kthSmallest(root, k);
    return 0;
}

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

Run Code

Output: 4

Output

For K=4
Inorder traversal for the constructed BST will be:

1 2 3 4 5 6 7

         ^

      4th element

Complexity analysis

Time Complexity: We run iterative inorder traversal till K becomes 0, so the time complexity will be O(K+H) where H is the tree's height because we also go till the depth.

Space Complexity: O(H) space complexity for stack size, where H is the height of the tree.

Frequently Asked Questions

What will be the time complexity of common operations in self-balancing binary search trees?

All three operations, i.e., lookup, delete, and insertion, take O(log N) time, where N is the number of nodes in the BST.

What is the difference between red-black trees and AVL trees?

Both AVL trees and red-black trees are self-balancing binary search trees, where all three major operations take O(log N) time
But AVL trees are more rigidly balanced, whereas red-black trees are comparatively loosely balanced; thus, AVL trees have faster lookup time.
Due to rigidity, insertion takes more time in AVL than in red-black trees.

What are the applications of Red black trees?

Red Black trees have average add, remove, and look-up performance, while AVL trees have faster look-ups at the expense of slower add and remove. The following are some uses for red-black trees:
Java.util.TreeSet and java.util.TreeMap
C++ STL: map, multimap, and multiset

Conclusion

In this article, we have learned a very important medium-level question on BSTs. We found Kth smallest number in the given BST.

We hope this blog has helped you enhance your knowledge of Binary Search Trees and improve your problem-solving skills. To learn more about BSTs and solve more such questions, refer to our articles from Fix BST, Binary Search Tree | Learn & Practice from Coding Ninjas Studio, and Binary Tree To BST. Practice more DSA problems from our Problems List of various companies.

Check out this problem - Next Smaller Element

You can also refer to our guided paths on the Coding Ninjas Studio platform to learn more about DSA, DBMS, Competitive Programming, Python, Java, JavaScript, etc. 

Refer to the links problems, top 100 SQL problems, resources, and mock tests to enhance your knowledge.

For placement preparations, visit interview experiences and interview bundle.

Do upvote our blog to help other ninjas grow. Happy Coding!