USA: +1 (725) 712-1730 
Sign in
Suppose we define a binary tree node as follows: /* * struct for a single node in a binary tree. info contains the data * stored in this node. left and right contain pointers to the left and * right subtrees respectively. leftCnt contains the number of keys * stored in the left subtree. * * All of the data stored in the left subtrees is smaller than infor. * All of the data stored in the right subtrees is larger than info. */ struct node { into info: struct node *left: struct node *right: int leftCnt: }: typedef struct node node: Write a function findKthKey which finds and returns the k^th smallest info value stored in the tree. You can assume the tree is non-empty (your function can be either iterative or recursive). int findKthKey (node *tree, int k) {
Expert Answer
/*Below is the Definition of the Function you need to write*/
int findkthkey(node *tree, int k)
{
int returnValue = -1;
if( tree )
{
/* A pointer for traversal */
node *pointerTraverse = tree;
/* Find k-th smallest */
while(pointerTraverse)
{
if( (pointerTraverse->leftCnt + 1) == k )
{
returnValue = pointerTraverse->info;
break;
}
else if( k > pointerTraverse->leftCnt )
{
/* Go to right subtree If There are less no. of nodes on left subtree
*/
k = k – (pointerTraverse->leftCnt + 1);
pointerTraverse = pointerTraverse->right;
}
else
{
/* Node is on Left */
pointerTraverse = pointerTraverse->left;
}
}
}
return returnValue;
}
/*Let me know, if you face any difficulty in executing this*/
