Tree

Problem
Check if a given tree is a Binary Search Tree ( BST ).
The tree shown below is a BST.

Solution
We need to validate that properties of BST are satisfied at each of the nodes.
Suppose we start at root node X . If maximum value in the left subtree is less than X -> data and minimum value in the right subtree is greater than X -> data , then BST properties are satisfied and we will recursively validate the properties for other nodes. If all the nodes are validated, then the Binary Tree is a Binary Search Tree .

```#include<iostream>
using namespace std;

// node structure
typedef struct tree_node
{
int value;
struct tree_node *left, *right;
}node;

// create a new node
node *getNewNode(int value) {
node *new_node = new node;
new_node->value = value;
new_node->left = NULL;
new_node->right = NULL;
return new_node;
}

// create the tree
node *createTree() {
node *root = getNewNode(25);
root->left = getNewNode(15);
root->right = getNewNode(30);
root->left->left = getNewNode(5);
root->left->right = getNewNode(20);
root->left->left->left = getNewNode(2);
root->right->right = getNewNode(40);
return root;
}

// get the maximum value in a subtree
int getMaxVal(node *temp) {
while(temp->right != NULL)
temp = temp->right;
return temp->value;
}

// get the minimum value in a subtree
int getMinVal(node *temp) {
while(temp->left != NULL)
temp = temp->left;
return temp->value;
}

// checks if the input tree is a BST
bool isBST(node *root) {
if (root == NULL) return true;
if (root->left && getMaxVal(root->left) > root->value)
return false; // BST property violation
if (root->right && getMinVal(root->right) <= root->value)
return false; // BST property violation
if (!isBST(root->left) || !isBST(root->right))
return false;
return true;
}

//main
int main() {
node *root = createTree();
bool is_bst = isBST(root);
if (is_bst)
cout<<"\nInput tree is a BST";
else
cout<<"\nInput tree is not a BST";
cout<<endl;
return 0;
}```