## Description

- (100 pts) Write a program to nd 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 eld
*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*eld of the nodes when you insert and delete from the tree. To nd the kth smallest node, you need to use the*count*eld 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 eld 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 eld for a node is shown on top left of the node.

4

10 | |||

2 | 2 | ||

6 | 14 | ||

1 | 1 | 1 | 1 |

4 | 8 | 12 | 16 |

Figure 1: Binary Search Tree

Sample execution for above tree is given below

fox01>assign4

Enter the set of numbers for the tree

10 6 14 4 8 12 16

Enter k

5

Result = 12

*Submit your program electronically using the blackboard system*

* *

*The program you submit should be your own work. Cheating will be reported to oﬃce of academic integrity. Both the copier and copiee will be held responsible.*