Problem Statement:
You are given a BST root node, you need to find the max and min value.
Solution
To get the min value, traverse the node from root to left recursively until left node is NULL.
To get the max value, traverse the node from root to right recursively until right node is NULL.
Solution in C++
#include<iostream>
#include<vector>
#include<string>
using namespace std;
struct Node
{
int data;
Node *left;
Node *right;
};
//global root declaration
Node *root;
Node* insert(int num, Node* root)
{
if(root == NULL)
{
root = new Node;
root->data = num;
root->left = root->right = NULL;
}
else if(num < root->data)
root->left = insert(num, root->left);
else if(num > root->data)
root->right = insert(num, root->right);
return root;
}
Node* findMax(Node* root)
{
if(root == NULL)
return NULL;
else if(root->right == NULL)
return root;
else
return findMax(root->right);
}
Node* findMin(Node* root)
{
if(root == NULL)
return NULL;
else if(root->left == NULL)
return root;
else
return findMin(root->left);
}
void inorder(Node *root)
{
if(root == NULL)
return;
inorder(root->left);
cout << root->data << " ";
inorder(root->right);
}
int main()
{
root = insert(10, root);
root = insert(30, root);
root = insert(20, root);
root = insert(50, root);
root = insert(60, root);
root = insert(25, root);
root = insert(15, root);
cout<<"\nThe values displayed using inorder traversal = "<<endl;
inorder(root);
Node *max_value = findMax(root);
cout<<"\n\nThe maximum value is "<< max_value->data <<endl;
Node *min_value = findMin(root);
cout<<"\nThe minimum value is "<< min_value->data <<endl;
return 0;
}
Output:
The values displayed using inorder traversal =
10 15 20 25 30 50 60
The maximum value is 60
The minimum value is 10