CareerCup

/* check for BST */
	private static boolean isBST(BSTNode root) {
		if (root == null)
			return true;

		if (root.getLeft() != null && findMax(root.getLeft()) > root.getData())
			return false;
		if (root.getRight() != null
				&& findMin(root.getRight()) < root.getData())
			return false;

		if (!(isBST(root.getLeft())) || (!isBST(root.getRight())))
			return false;
		return true;
	}

/* Check for binary tree whether its binary search tree */
	private static boolean isBST(BSTNode root, int prev) {
		if(root==null)
			return true;
		if(!isBST(root.getLeft(),prev))
			return false;
		if(root.getData()<prev)
			return false;
		prev=root.getData();
		
		return isBST(root.getRight(),prev);
	}

The inorder traversal of the tree should be sorted.

BOOL IsBST(Node *Root)
{
    If(NULL == Root) return TRUE;
    int min = findMin(Root);
    int max = findMax(Root);
    return IsBST(Root, min-1, max+1);
}
BOOL IsBST(Node *Root, int MIN, int MAX)
{
    If(NULL == Root) return TRUE;
    return ( (Root->info > MIN) && 
             (Root->info < MAX) && 
	     IsBST(Root->Left, MIN, Root->Info+1) && 
	     IsBST(Root->Right, Root->Info-1, MAX) );
}

bool isBST(struct node *node)
{
    return( isBSTHelper(node, INT_MIN, INT_MAX));
}
bool isBSTHelper(struct node *node, int min, int max)
{
  if( node == NULL)  
      return true;
  if( node->data < min || node->data > max )     
      return false;
  return ( isBST(node->left, min, node->data) &&
               isBST(node->right, node->data, max));
}

boolean isBst(Node root){
if (root == null) return true;
else{
bool temp;
if(node->left != null && node->left->value < node->value)
temp = true;
if(node->right != null && node->right->value > node->value)
temp = true;
if(temp)
return isBst(node->left) && isBst(node->right) ;
else
return false;
}
}

bool flag  = true;
int max_encountered = NEGATIVE_INFINITY;
void checkInorder(Node root){
  if(root == null) return;
  if(!flag){
    println("Not a BST");
  }
  if(  flag && root.left != null)  
    checkInorder(root.left);
  if( flag && root.data > max_encountered){
    max_encountered = root.data
  }else{
    flag = false;
  }
   if( flag && root.right != null)  
    checkInorder(root.right);
}

public Boolean IsBst(Node node) {

IsValidBST(root,Integer.MIN_VALUE,Integer.MAX_VALUE);

bool IsValidBST(BinaryNode node, int MIN, int MAX)
{
if(node == null)
return true;
if(node.element > MIN
&& node.element < MAX
&& IsValidBST(node.left,MIN,node.element)
&& IsValidBST(node.right,node.element,MAX))
return true;
else
return false;
}

boolean isBst(Node n, int min, int max) {
if(n == null) return true;
if( n.data <= max || n.data > min) return false;
else return ( isBst(n.left, min, n.data) |&&
isBst(n.right, n.data, max));
}

first call will be isBst(root, -sentinel, sentinel); // sentinel = largest possible value.

If inorder traversal is in sorted order, then the tree is BST. Am I missing any other scenarios to consider ?

bool isBST(node* root)
{
bool isBst = true;
if (NULL == root)
return true;
if (root != NULL)
{
if (root->lchild != NULL && ((root->data) < (root->lchild->data))) {
isBst = false;
}
if (root->rchild != NULL && ((root->data) > (root->rchild->data))) {
isBst = false;
}
isBST(root->lchild);
isBST(root->rchild);
}
return isBst;
}