We are given the code for a Binary Search Tree with built-in operations INSERT,

Question

We are given the code for a Binary Search Tree with built-in operations INSERT, DELETE, SEARCH, and FIND-MINIMUM-VALUE. In the node struct, we create additional attributes minval (smallest value present in the node's subtree), maxval (largest value present in the node's subtree) and mingap (the difference of the two closest numbers in the node's subtree). Modify any of the built-in functions necessary to keep the additional attributes updated without affecting the time complexity of these functions.

I believe we only need to modify the INSERT and DELETE functions, but I am not sure...

Explanation / Answer

Answer :

int maxValue(BSTNode *node, int max = INT_MIN)
{
if(node == NULL)
return max;

if(node->data > max)
max = node->data;
max = maxValue(node->left, max);
max = maxValue(node->right, max);
return max;
}

int minValue(BSTNode *node, int min = INT_MAX)
{
if(node == NULL)
return min;

if(node->data > min)
min = node->data;
min = minValue(node->left, min);
min = minValue(node->right, min);
return min;
}

int mingap(BSTNode *node,int mingap=INT_MINGAP)
{
   if(node==NULL)
       return mingap;
  
   if(node->data > max)
   max = node->data;
   max = maxValue(node->left, max);
   max = maxValue(node->right, max);
   int c=max;

   if(node->data > min)
   min = node->data;
   min = minValue(node->left, min);
   min = minValue(node->right, min);
   int h=min;

   mingap=c-h;

   return mingap;

}

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.