Finding kth smallest element in an array using Binary Search Tree

Question

The question is to find the "Kth" smallest element in an array. https://practice.geeksforgeeks.org/problems/kth-smallest-element/0

Now I did see the given techniques but cannot understand them properly. My first intuition after seeing the question was to create a BST from the given array and use the InOrder Traversal of the BST to find the "Kth" smallest element of the array. Here is the code of my approach.

/*

#include <bits/stdc++.h>
using namespace std;
struct node{
    int data;
    node* left;
    node* right;
};
vector<int> v;//sorted vector
node* insert(node* root,int data){
    if(!root){
        root = new node();
        root->data = data;
        root->left = NULL;
        root->right = NULL;
        return root;
    }
    if(root->data > data)
    root->left = insert(root->left , data);
    else
    root->right = insert(root->right , data);
    
    return root;
}
void inOrder(node* root){
    if(!root)
    return;
    
    inOrder(root->left);
    v.push_back(root->data);
    //cout<<root->data<<" ";
    inOrder(root->right);
}
int main() {
    int t;
    cin>>t;
    while(t--){
        node* root = NULL;
        int n,el;
        cin>>n;
        for(int i=0;i<n;i++){
            cin>>el;
            root = insert(root,el);
        }
        int k;
        cin>>k;
        inOrder(root);
        cout<<v[k-1]<<endl;
        v.clear();
    }
    return 0;
}

*/ Now this according to me should be O(n) in the worst case, but I am not sure. This code gives me a "TLE". Help me fix this code. This is probably the first time I got an intuition to solve a question via a BST so I would like to complete this question via this approach only.

Your code is not O(n) but O(n*2) in worst case and O(n*log n) on average. I expect the TLE occurs on data deliberately chosen to bring out the worst case behaviour. The worst case would happen with (for instance) already sorted data when your BST would degenerate into a linked list. This is a well known problem with BST. The good news is that the code appears to be correct if inefficient. — john
And why is it O(n^2)? Is it because every insertion is O(n) and calling it 'n' times make it O(n^2)? So the approach cannot be used? — Parth Sharma
Typo in the comment above. Of course I meant O(n^2), i.e. quadratic time, not O(n*2). — john

Lazy Ren Lazy Ren · Accepted Answer · 2020-09-20T06:16:05

You simply cannot solve this question with BST.

Question cleary states that Expected Time Complexity: O(N).

But insert operation itself takes average O(logN), worst O(N).LINK
You are doing insert operation N times. Hence,

for(int i=0;i<n;i++){
  cin>>el;
  root = insert(root,el);
}

This code fragment already took O(NlogN) or worst O(N^2).

The best solution is using pivot and partitioning just like quick sort.

But instead of fully sort the arrays, you discard one partition that is irrelevant, and keep partitioning recursively on one partition only.

Check the best solution link for detail info.

Finding kth smallest element in an array using Binary Search Tree

1 Answers