check for bst

1// C++ program to check if a given tree is BST. 
2#include <bits/stdc++.h> 
3using namespace std; 
4
5/* A binary tree node has data, pointer to 
6left child and a pointer to right child */
7struct Node 
8{ 
9	int data; 
10	struct Node* left, *right; 
11}; 
12
13// Returns true if given tree is BST. 
14bool isBST(Node* root, Node* l=NULL, Node* r=NULL) 
15{ 
16	// Base condition 
17	if (root == NULL) 
18		return true; 
19
20	// if left node exist then check it has 
21	// correct data or not i.e. left node's data 
22	// should be less than root's data 
23	if (l != NULL and root->data <= l->data) 
24		return false; 
25
26	// if right node exist then check it has 
27	// correct data or not i.e. right node's data 
28	// should be greater than root's data 
29	if (r != NULL and root->data >= r->data) 
30		return false; 
31
32	// check recursively for every node. 
33	return isBST(root->left, l, root) and 
34		isBST(root->right, root, r); 
35} 
36
37/* Helper function that allocates a new node with the 
38given data and NULL left and right pointers. */
39struct Node* newNode(int data) 
40{ 
41	struct Node* node = new Node; 
42	node->data = data; 
43	node->left = node->right = NULL; 
44	return (node); 
45} 
46
47/* Driver program to test above functions*/
48int main() 
49{ 
50	struct Node *root = newNode(3); 
51	root->left	 = newNode(2); 
52	root->right	 = newNode(5); 
53	root->left->left = newNode(1); 
54	root->left->right = newNode(4); 
55
56	if (isBST(root,NULL,NULL)) 
57		cout << "Is BST"; 
58	else
59		cout << "Not a BST"; 
60
61	return 0; 
62} 
63