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