CS 2123 Data Structures Due Friday March 25 1. (100 pts) Write a program to find
ID: 3680189 • Letter: C
Question
CS 2123 Data Structures Due Friday March 25 1. (100 pts) 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 nmber 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 mode and decide whether kth smallest node is in the left subtree or the right subtree and follow that subtree, Node structure with count ficld is as follow struct node int key: int count struct node left, right typedef struet node node: Consider the binary search tree given below Count field for a node is shown on top left of the node, 10 16 Figure 1: Binary Search Tree Sample execution for above tree is given below foxoaasig4 Enter the set of nusbers for the tree 10 6 14 4 8 12 16 Enter k Result 12 Submit your program electronically using the blackboard system The program you submit should be your own work. Cheating will be reported to office of academic Both the copier a nd will be held responsible. be heldExplanation / Answer
KthSmallestElementinaBST.h
int kthSmallest(TreeNode* root, int k) {
int ret = 0, count = 0;
function<void(TreeNode*) > solve = [&](TreeNode *node)
{
if (!node) return;
solve(node->left);
if (++count == k)
{
ret = node->val;
return;
}
solve(node->right);
};
solve(root);
return ret;
}