A program to check if a binary tree is BST or not | C ++ program to check if a given tree is BST . ; A binary tree node has data , pointer to left child and a pointer to right child ; Returns true if given tree is BST . ; Base condition ; 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 right node exist then check it has correct data or not i . e . right node ' s ▁ data ▁ ▁ should ▁ be ▁ greater ▁ than ▁ root ' s data ; check recursively for every node . ; Helper function that allocates a new node with the given data and NULL left and right pointers . ; Driver program to test above functions
#include <bits/stdc++.h> NEW_LINE using namespace std ; struct Node { int data ; struct Node * left , * right ; } ; bool isBST ( Node * root , Node * l = NULL , Node * r = NULL ) { if ( root == NULL ) return true ; if ( l != NULL and root -> data <= l -> data ) return false ; if ( r != NULL and root -> data >= r -> data ) return false ; return isBST ( root -> left , l , root ) and isBST ( root -> right , root , r ) ; } struct Node * newNode ( int data ) { struct Node * node = new Node ; node -> data = data ; node -> left = node -> right = NULL ; return ( node ) ; } 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 ; }