# find kth smallest element in binary search tree

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.

## Leave a Reply