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