You are given a binary search tree. Write c or c++ program to find kth smallest element in it. For in  given bst the 3 is first smallest and 4 is 2nd smallest.

Let us write a program to find 2nd smallest in binary search tree considering above BST as input.

## c program find kth smallest element in binary search tree

```#include <stdio.h>
#include <malloc.h>

typedef struct Tree
{
struct Tree* left;
int val;
struct Tree* right;
}BST;

int index = 0;
int arr [10000];

void push(int val)
{
arr [index++] = val;
}

BST* create_node(int val)
{
BST* tmp = NULL;
tmp = (BST*) malloc(sizeof(BST));
tmp->left = NULL;
tmp->right = NULL;
tmp->val = val;
return tmp;
}

void inOrder(BST *root)
{
if (root)
{
inOrder(root->left);
push(root->val);
inOrder(root->right);
}
}

int FindKthSmallest(BST* root, int k)
{
inOrder(root);
return arr [ k - 1];
}

int main()
{
// prepare input
BST *tree = create_node(5);
tree->left = create_node(3);
tree->right = create_node(6);
tree->left->right = create_node(4);

int smallest = FindKthSmallest(tree, 2);
printf("%d\n", smallest);

return 0;
}
```

Output : 4

## How Solution 1 works:

The in-order traversal of binary search tree produces elements in sorted order ( from smallest to largest). We are simply traversing BST in-order and keep all elements into an array.