Programming Assignment 3 Implement 2 functions int minTNode

Programming Assignment 3:

Implement 2 functions, int min(TNode *) and int max(TNode *) that take a pointer to a TNode and return the smallest (min) and largest (max) node in the BST. Implement two versions of each function, one version using a loop, the other using recursion. To find the largest value in a BST with a loop, you need to keep moving the node pointer right until you reach a node with a null right child. The data at that node is the max. Smallest value is found by going left as far as possible. Recursively, to find the largest value, if node t has no right child, it contains the answer, otherwise the answer is the largest value in the right subtree. Test the functions on the BST built in the last assignment.

USE THIS CODE:

Solution

The maximum and minimum element in the BST can be found at the rightmost and leftmost nodes respectively.

The following four implementations show how to find the maximum and minimumElement in BST recursively and non-recursively.

1) Non -Recursive implementation to find Maximum element in BST

int max(TNode* root){

int max = 0;

TNode* temp = root; //temp is a pointer that points to the root of the BST

//Loop until we reach the rightmost end of the BST

while(temp->right !=NULL){

temp = temp->right;
}

//retrieve the value of the rightmost node into the variable max and finally return
max = temp.data;

return max;
}

2) Recursive implementation to find Maximum element in BST
int max(TNode* root){

int max_val = 0;

// if the node is the rightmost node in the BST, retrieve the value in the node
if(root->right==NULL){
max_val = root.data;
}

// else call the max function recursively so that you get to the rightmost end of the BST
if(root->right != NULL){
   max_val = max(root->right);

}

return max_val;

}

3) Non -Recursive implementation to find Minimum element in BST

int min(TNode* root){

int min_val = 0;

TNode* temp = root;

//Loop until we reach the leftmost end of the BST
while(temp->left !=NULL){

temp = temp->left;
}

//retrieve the value of the leftmost node into the variable min_val and finally return
min_val = temp.data;

return min_val;
}

4) Recursive implementation to find Maximum element in BST
int min(TNode* root){
int min_val = 0;
// if the node is the leftmost node in the BST, retrieve the value in the node
if(root->left==NULL){
min_val = root.data;
}
// else call the min function recursively so that you get to the leftmost end of the BST
if(root->left != NULL){
   min_val = min(root->left);

}

return min_val;

}