Finding kth-smallest element in a BST

general
, , , ,
1

Struggling hard to understand the function: node* k_smallest_elementUtil(node* tree, int k, int &count). Any help will be appreciated. Thanks.

 #include<iostream>
 using namespace std;

 struct node{
int data;
node *left;
node *right;

};

 node *newnode(int data){
node *new_node=new node;
new_node->data=data;
new_node->left=NULL;
new_node->right=NULL;
return new_node;

}

 node *insert(node *tree, int data){
if(tree==NULL) return newnode(data);
if(data<tree->data){
	tree->left=insert(tree->left,data);
}
else{
	tree->right=insert(tree->right,data);
}
return tree;

}

 node* k_smallest_elementUtil(node* tree, int k, int &count){
if(tree==NULL) return tree;

node *left=k_smallest_elementUtil(tree->left,k,count);
if(left) return left;

count++;
if(count==k)  return tree;

node* right=k_smallest_elementUtil(tree->right,k,count);
if(right) return right;

return NULL;

}

node* k_smallest_element(node* tree, int k){
int count=0;
return k_smallest_elementUtil(tree,k,count);

}

int main(){
int k=5;
node *tree=NULL;
tree=insert(tree,20);
insert(tree,8);
insert(tree,22);
insert(tree,4);
insert(tree,12);
insert(tree,10);
insert(tree,14);
node *temp=k_smallest_element(tree,5);
2

Hi Shubh,

Firstly, let’s recall a BST is a binary tree in which the left-child’s data is less than it’s parent’s data, and the parent’s data is smaller than that of it’s right child.

Think what you’d have done if you had to find the K-th smallest element in an array instead of a BST.
Maybe you’d sort the array , iterate till you reach the K-th element (right?).

Similarly if we can sort the data somehow present in the BST, our purpose would be served.
Now, recall that the In-order traversal of a BST always produces a sorted list of data(increasing).

So, the function k_smallest_elementUtil does just the same, it keeps a counter, count to keep track of elements traversed so far. The moment we get to know that we’ve traversed K elements , we simply return that particular node.

Hope it helps!

3 Likes
3

At every node, store 3 things in a BST, Node\ Value, TotalL and TotalR which denotes the total elements in the Left Subtree and Right subtree respectively.

At a particular node say N, lets say, TotalL is y. Now, we can come up with a recursive definition.

If y == k-1, the value at this N is the answer.

If y\ < k-1, that means in the Right subtree we have to find the (k-y)^{th} smallest element.

If y\ > k - 1, then in the Left subtree, we have to find the k^{th} smallest element.

This solution gives the answer in O(Height) which in case of Balanced BST in O(log\ n).

4

@ashutosh_cric sometimes non-conventional thinking is key to problem and you proved it… thanks…

1 Like