Binary Search Trees: Kth smallest Element in a BST

Problem Statement:

You are given BST and a kth element in the given tree.

Then you need to give the kth smallest element.

Solution

Solution is very simple.

We will take in-order traversal and store it an array.

Then we take the kth smallest element.

Solution in C++

#include<iostream>
#include<vector>
#include<string>
#include<set>

using namespace std;


struct Node
{
    int data;
    struct Node *left, *right;
};

Node *get_new_node(int item)
{
    Node *temp =  new Node;
    temp->data = item;
    temp->left = temp->right = NULL;
    return temp;
}
 
Node* insert_into_bst(Node* node, int data) 
{ 
    if (node == NULL) return get_new_node(data); 
  
    if (data < node->data) 
        node->left  = insert_into_bst(node->left, data); 
    else if (data > node->data) 
        node->right = insert_into_bst(node->right, data);    
  
    return node; 
} 

void print_inorder(Node* Node) 
{ 
    if (Node == NULL) 
        return; 
    print_inorder(Node->left); 
    cout<<" "<<Node->data; 
    print_inorder(Node->right); 
} 

void inorder(Node* root, vector<int> &res)
{
  if(!root)
      return;
  inorder(root->left, res);
  res.push_back(root->data);
  inorder(root->right,res);
  
}

int kthSmallest(Node* root, int k)
{
  if(!root)
      return -1;
  vector<int> arr;
  inorder(root, arr);
  return arr[k-1];

}



int main()
{
    Node *root_1 = NULL; 
    root_1 = insert_into_bst(root_1, 1); 
    insert_into_bst(root_1, 2); 
    insert_into_bst(root_1, 3); 
    insert_into_bst(root_1, 4); 
    insert_into_bst(root_1, 5); 

    cout<<"The kth smallest element is "<< kthSmallest(root_1, 2)<<endl;

    return 0;
}

Output:

The kth smallest element is 2