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);
```

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

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).

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

1 Like