Question & Answer: Suppose we define a binary tree node as follows: /* * struct for a single node in a binary tree. info contains t…..

5. Binary Tree (3 points) Suppose we define a binary tree node as follows: a binary tree. into contains the data nunber of keys ssruct for a tored in thi8 node. 1.ft and right node in - right subtrees respectively leftCat - stored in the left subtree reapectivelcontais poisters to the lets and A11 of the data stored in the lett subtree ss snallerh data stored in the right subtres is larger struct node int into: struct node -left etruct node right: int leftCnt; typedet struct node node; Write a function findKthKey which finds and returns the kt smallest info value stored in the tree. You can assume the tree is non-empty (your function can be either iterative or recursive). Hint: It may make your search simpler to use the leftCnt stored in each node to decide if you should go down the left or right subtree. Going to the right will decrease the k value for your search by the leftCnt. int findKthKey (node tree, int k)

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*/

Still stressed from student homework?
Get quality assistance from academic writers!