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;

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)

int FindKthSmallest(BST* root, int k)
	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.

Related Contents to follow