This Program is to find maximum element between two nodes of binary search tree.Let's learn it by the help of example:
Input : Tree elements are : 1 2 3 5 6 4 7 8 9 10
Output : Enter 2 value to find the maximum no. between them : 5 9
Maximum no. is : 9
Program :
//C++ program to find maximum element between two nodes of binary search tree
using namespace std;
// tree nod
struct Node
{
int data;
Node *left, *right;
};
// returns a new tree Node
Node* newNode(int data)
{
Node* temp = new Node();
temp->data = data;
temp->left = temp->right = NULL;
return temp;
}
// A function to create binary search tree.
Node* Tree(Node* temp, int data )
{
// If the tree is empty, return a new node
if (temp == NULL)
return newNode(data);
// Otherwise, recur down the tree
if (data < temp->data)
temp->left = Tree(temp->left, data);
else
temp->right = Tree(temp->right, data);
//return the (unchanged) node pointer
return temp;
}
// Return the maximum element between a Node
int maxelement(Node *temp, int key)
{
Node *temp1 = temp;
int maximum = INT_MIN;
while (temp -> data != key)
{
if (temp -> data > key)
{
maximum = max(maximum, temp -> data);
temp = temp -> left;
}
else
{
maximum = max(maximum, temp -> data);
temp = temp -> right;
}
}
return max(maximum, key);
}
// Return maximum element in the path between two given Node of binary search tree.
int maximumElement(struct Node *root, int key, int key1)
{
Node *temp = root;
while ((key < temp -> data && key1 < temp -> data) ||
(key > temp -> data && key1 > temp -> data))
{
// Checking if both the Node lie on the left side of the parent temp.
if (key < temp -> data && key1 < temp -> data)
temp = temp -> left;
// Checking if both the Node lie on the right side of the parent temp.
else if (key > temp -> data && key1 > temp -> data)
temp = temp -> right;
}
// Return the maximum elements occur in path.
return max(maxelement(temp, key), maxelement(temp, key1));
}
// Driver Code
int main()
{
int n, a, b, arr[20],size;
Node *root = new Node;
root = NULL;
cout<<"Enter the size of array : ";
cin>>size;
cout<<"Enter the elements in array : ";
for(int i=0;i<size;i++)
{
cin>>arr[i];
}
// Construct the binary tree.
for(int i = 0; i < size; i++)
root = Tree(root, arr[i]);
cout<<"Enter 2 value to find the maximum no. between them : ";
cin>>a>>b;
cout <<"Maximum no. is : "<< maximumElement(root, a, b) << endl;
return 0;
}
Comments