Posted on by Kalkicode
Code Binary Search Tree

Find kth smallest element in BST c

Find the kth smallest node in binary tree

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

Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment