CareerCup

int FindMax(Tree *root)
{
//Assuming root is not null.
if(root==NULL)
return 9999;
while(root->right)
root=root->right;
return root->element;
}

int FindMin(Tree *root)
{
//Assuming root is not null.
if(root==NULL)
return -9999;
while(root->left)
root=root->left;
return root->element;
}

bool isBST(Tree *root)
{
if(root==NULL)
return true;
else if(((root->left!=NULL) && (FindMax(root->left)>root->element))||
((root->right!=NULL) && (FindMin(root->right)<root->element)))
return false;
else
return (isBST(root->right) && isBST(root->left));
}


The idea is to compare root's element with the maximum element in the left subtree and root's element with the minimum element in the right subtree

bool isBST(TreeNode * root, int * pMin=NULL, int * pMax=NULL)
{
   if (!root) return true;
   if (pMin && root->data <= *pMin) return false;
   if (pMax && root->data > *pMax) return false;
   return isBST(root->left, pMin, &root->data) &&
          isBST(root->right, &root->data, pMax);
}

inorder traversal should be sorted

IsBST(Tree *node)
{
    return IsBST(node, -infinity, infinity);
}
  
IsBinarySearchTree(Tree *node, int lower, int higher)
{
    if (node == null) return true;
    
    if (node->value < lower || node->value > higher) return false; 
  
    return IsBinarySearchTree(node->left, lower, node->value) && IsBinarySearchTree(node->right, node->value, higher); 
}

Boolean IsBST(Node curNode)
{
static int lastValue = MIN_INT;
if (curNode == null)
return true;
if (!IsBST(curNode->left)
return false;
if (curNode->value < lastValue)
return false;
lastValue = curNode->value;
return IsBST(curNode->right);
}