Find kth smallest element in BST c

C program for Find kth smallest element in BST. Here more solutions.

// Include header file
#include <stdio.h>
#include <stdlib.h>

// C program for
// K’th smallest element in Binary Search Tree
typedef struct TreeNode
{
	// Define useful field of TreeNode
	int data;
	struct TreeNode * left;
	struct TreeNode * right;
}TreeNode;

TreeNode * getTreeNode(int data)
{
	// Create dynamic memory of TreeNode
	TreeNode * ref = (TreeNode * ) malloc(sizeof(TreeNode));
	if (ref == NULL)
	{
		// Failed to create memory 
		return NULL;
	}
	ref->data = data;
	ref->left = NULL;
	ref->right = NULL;
	return ref;
}
typedef struct BinarySearchTree
{
	// Define useful field of BinarySearchTree
	struct TreeNode * root;
	int counter;
	struct TreeNode * element;
}BinarySearchTree;

BinarySearchTree * getBinarySearchTree()
{
	// Create dynamic memory of BinarySearchTree
	BinarySearchTree * ref = (BinarySearchTree * ) malloc(sizeof(BinarySearchTree));
	if (ref == NULL)
	{
		// Failed to create memory 
		return NULL;
	}
	ref->root = NULL;
	return ref;
}
// Insert a node element
TreeNode * insert(BinarySearchTree * ref, 
                  TreeNode * node, int data)
{
	if (node != NULL)
	{
		if (node->data >= data)
		{
			// When new element is smaller or equal to current node
			node->left = insert(ref,node->left, data);
		}
		else
		{
			// When new element is higher to current node
			node->right = insert(ref, node->right, data);
		}
		// Important to manage new node
		return node;
	}
	else
	{
		return getTreeNode(data);
	}
}
// Find the kth smallest node in BST
void findKthSmallest(BinarySearchTree * ref, 
                     TreeNode * node, int k)
{
	if (node != NULL)
	{
		// Visit left subtree
		findKthSmallest(ref, node->left, k);
		if (ref->counter == k)
		{
			// Stop recursion
			return;
		}
		if (ref->element == NULL || ref->element->data < node->data)
		{
			// Modified counter variable by one
			ref->counter++;
			// Collect possible result
			ref->element = node;
		}
		// Visit right subtree
		findKthSmallest(ref, node->right, k);
	}
}
void printKthSsmallest(BinarySearchTree * ref, int k)
{
	if (k <= 0)
	{
		// When given k is not valid positive values
		printf("Invalid node position %d\n", k);
	}
	else if (ref->root == NULL)
	{
		// When BST are no have elements
		printf("Empty Binary Search Tree");
	}
	else
	{
		// Reset values
		ref->counter = 0;
		ref->element = NULL;
		// Find result
		findKthSmallest(ref, ref->root, k);
		if (ref->counter < k)
		{
			// If In case given kth smallest node are
			// Not exist in binary search tree, then
			printf("Given %d smallest node are not exist %d\n", k, ref->counter);
		}
		else
		{
			printf("[%d] smallest node : %d\n", k,ref->element->data);
		}
	}
}
// Handle request to add new node
void addNode(BinarySearchTree * ref, int key)
{
	ref->root = insert(ref, ref->root, key);
}
int main()
{
	BinarySearchTree * tree = getBinarySearchTree();
	/*
	    Make Tree
	    ----------
	        7
	       / \ 
	      /   \
	     4     9
	    / \   / \
	   3   5 8   10
	      /    
	     4     
	*/
	// Add node
	addNode(tree, 7);
	addNode(tree, 4);
	addNode(tree, 3);
	addNode(tree, 5);
	addNode(tree, 9);
	addNode(tree, 8);
	addNode(tree, 10);
	addNode(tree, 4);
	// Testing
	printKthSsmallest(tree, 6);
	printKthSsmallest(tree, 4);
	printKthSsmallest(tree, 3);
	return 0;
}

Output

[6] smallest node : 9
[4] smallest node : 7
[3] smallest node : 5