algorithm for checking if binary tree is binary search tree or not code example

Example: check for bst

// C++ program to check if a given tree is BST. 
#include <bits/stdc++.h> 
using namespace std; 

/* A binary tree node has data, pointer to 
left child and a pointer to right child */
struct Node 
{ 
	int data; 
	struct Node* left, *right; 
}; 

// Returns true if given tree is BST. 
bool isBST(Node* root, Node* l=NULL, Node* r=NULL) 
{ 
	// Base condition 
	if (root == NULL) 
		return true; 

	// if left node exist then check it has 
	// correct data or not i.e. left node's data 
	// should be less than root's data 
	if (l != NULL and root->data <= l->data) 
		return false; 

	// if right node exist then check it has 
	// correct data or not i.e. right node's data 
	// should be greater than root's data 
	if (r != NULL and root->data >= r->data) 
		return false; 

	// check recursively for every node. 
	return isBST(root->left, l, root) and 
		isBST(root->right, root, r); 
} 

/* Helper function that allocates a new node with the 
given data and NULL left and right pointers. */
struct Node* newNode(int data) 
{ 
	struct Node* node = new Node; 
	node->data = data; 
	node->left = node->right = NULL; 
	return (node); 
} 

/* Driver program to test above functions*/
int main() 
{ 
	struct Node *root = newNode(3); 
	root->left	 = newNode(2); 
	root->right	 = newNode(5); 
	root->left->left = newNode(1); 
	root->left->right = newNode(4); 

	if (isBST(root,NULL,NULL)) 
		cout << "Is BST"; 
	else
		cout << "Not a BST"; 

	return 0; 
}