Implement a decrease-and conquer variable – size decrease algorithm for Finding the largest key in binary search tree.
APPROACH FOR FINDING MAXIMUM KEY
-
- TRAVERSING the element
- Simply move to the rightmost node
- As in the Binary search, the tree right node is the greatest
- So instead of traversing the whole tree at every level choose only the right subtree
- And go until you don’t have any right child node
- That node will have the largest key…
First of all, create a binary Search tree and insert the element follow this process:-
An element can only be inserted in a binary search tree if the appropriate location is found. Therefore, the given element which is to be inserted is first compared with the root node.
If the element is less than the root node then it is compared with the left child of the root node If the element is greater than the root node then it is compared with the right child of the root node.
Then binary search tree is left subtree of a node containing only node with keys lesser than the node keys.
The right subtree of a node contains only a node with a key greater than the node keys.
And use BINARY SEARCH TREE property and find the maximum value in the binary search tree
First Start from the root node and check the right of the root is not null go to the right of the root and check again
If the right root is null therefore it’s the maximum element.
Implement a decrease-and conquer variable – size decrease algorithm for Finding the largest key in the binary search tree.
#include<bits/stdc++.h>
using namespace std;
// A tree node using structure
struct node{
int data;
struct node *left ,*right;
};
// function to insert a new bst node
struct node *newnode(int key){
struct node*Node=(struct node*)malloc(sizeof(struct node));
Node->data=key;
Node->left=Node->right=NULL;
return (Node);
}
// function to insert a new node with given key
struct node*insert(struct node *temp,int data){
if(temp==NULL){
return(newnode(data));
}
if(data<temp->data)
temp->left=insert(temp->left,data);
else if(data>temp->data)
temp->right=insert(temp->right,data);
return temp;
}
// Returns maximum value in a given binary tree......................
int find_Maximum(node* root){
// Base case of find_maximum key
if (root == NULL)
return INT_MIN;
// Return maximum of 3 value
// first Root's data second Max in Left Subtree
// and laast Max in right subtree
int r = root->data;
int lr = find_Maximum(root->left);
int rr = find_Maximum(root->right);
if (lr > r)
r = lr;
if (rr > r)
r = rr;
return r;
}
// main function ...........................
int main(){
struct node *root=NULL;
root= insert(root,50);
insert(root,30);
insert(root,20);
insert(root,40);
insert(root,70);
insert(root,60);
insert(root,80);
// Function call .................................
cout << "Maximum key is " << find_Maximum(root) << endl;
return 0;
}
Output:
