In C: Write a program to find the kth smallest element in a binary search tree.
ID: 3681173 • Letter: I
Question
In C:
Write a program to find the kth smallest element in a binary search tree. Since we don't know how many elements are in each subtree, we can add a new field count to each node that stores the total number of elements that are in the left subtree and the current node. You need the update count field of the nodes when you insert and delete from the tree. To find the kth smallest node, you need to use the count field of the current node and decide whether kth smallest node is in the left subtree or the right subtree and follow that subtree. Node structure with count field is as follows struct node { int key Int count; struct node *left, *right; }; typedef struct node node; Consider the binary search tree given below. Count field for a node is shown on top left of the node Sample execution for above tree is given below foxO1 greaterthan ass ign4 Enter the set of numbers for the tree 10 6 14 4 8 12 16 Enter k 5 Result =12Explanation / Answer
The idea is to maintain rank or count of each node. We can keep track of elements in a subtree of any node while building the tree. Since we need K-th smallest element, we can maintain number of elements of left subtree in every node.
Assume that the root is having N nodes in its left subtree. If K = N + 1, root is K-th node. If K < N, we will continue our search (recursion) for the Kth smallest element in the left subtree of root. If K > N + 1, we continue our search in the right subtree for the (K – N – 1)-th smallest element. Note that we need the count of elements in left subtree only.
Time complexity: O(h) where h is height of tree.
Program code:
#include <stdio.h>
#include <stdlib.h>
#define ARRAY_SIZE(arr) sizeof(arr)/sizeof(arr[0])
typedef struct node_t node_t;
/* Binary tree node */
struct node_t
{
int data;
int lCount;
node_t* left;
node_t* right;
};
/* Iterative insertion
Recursion is least preferred unless we gain something
*/
node_t *insert_node(node_t *root, node_t* node)
{
/* A crawling pointer */
node_t *pTraverse = root;
node_t *currentParent = root;
// Traverse till appropriate node
while(pTraverse)
{
currentParent = pTraverse;
if( node->data < pTraverse->data )
{
/* We are branching to left subtree
increment node count */
pTraverse->lCount++;
/* left subtree */
pTraverse = pTraverse->left;
}
else
{
/* right subtree */
pTraverse = pTraverse->right;
}
}
/* If the tree is empty, make it as root node */
if( !root )
{
root = node;
}
else if( node->data < currentParent->data )
{
/* Insert on left side */
currentParent->left = node;
}
else
{
/* Insert on right side */
currentParent->right = node;
}
return root;
}
/* Elements are in an array. The function builds binary tree */
node_t* binary_search_tree(node_t *root, int keys[], int const size)
{
int iterator;
node_t *new_node = NULL;
for(iterator = 0; iterator < size; iterator++)
{
new_node = (node_t *)malloc( sizeof(node_t) );
/* initialize */
new_node->data = keys[iterator];
new_node->lCount = 0;
new_node->left = NULL;
new_node->right = NULL;
/* insert into BST */
root = insert_node(root, new_node);
}
return root;
}
int k_smallest_element(node_t *root, int k)
{
int ret = -1;
if( root )
{
/* A crawling pointer */
node_t *pTraverse = root;
/* Go to k-th smallest */
while(pTraverse)
{
if( (pTraverse->lCount + 1) == k )
{
ret = pTraverse->data;
break;
}
else if( k > pTraverse->lCount )
{
/* There are less nodes on left subtree
Go to right subtree */
k = k - (pTraverse->lCount + 1);
pTraverse = pTraverse->right;
}
else
{
/* The node is on left subtree */
pTraverse = pTraverse->left;
}
}
}
return ret;
}
/* Driver program to test above functions */
int main(void)
{
/* just add elements to test */
/* NOTE: A sorted array results in skewed tree */
int ele[] = { 20, 8, 22, 4, 12, 10, 14 };
int i;
node_t* root = NULL;
/* Creating the tree given in the above diagram */
root = binary_search_tree(root, ele, ARRAY_SIZE(ele));
/* It should print the sorted array */
for(i = 1; i <= ARRAY_SIZE(ele); i++)
{
printf(" kth smallest elment for k = %d is %d",
i, k_smallest_element(root, i));
}
getchar();
return 0;
}