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);
	}

This question can be easily misinterpreted. The conditioin

left_child < node < right_child

is not enough to make a binary tree a BST. Given a node n, all descendants to the left must be less than n's value. Likewise, all descendants to the right must be greater than n's value. These bounds must be passed forward in the search.

int check_bst(Node *p, int min, int max)
{
	if (p == 0)
		return 1;

	int value = p->value;

	if (value > max || value < min)
		return 0;

	return check_bst(p->left, min, value-1) 
		&& check_bst(p->right, value+1, max);
}

int is_bst(Node *root)
{
	int value = root->value;
	return check_bst(root->left, INT_MIN, value-1)
		&& check_bst(root->right, value+1, INT_MAX);
}

def isTreeBST(n,min,max):

	if(n==None):
		return True
	if(n.data<min or n.data>max):
		return False

	if(not(isTreeBST(n.left,min,n.data-1)) or not(isTreeBST(n.right,n.data+1,max))):
		return False


	return True

BOOL IsBST(BST *root, int *val)
{
BOOL bRet = TRUE;

if (NULL == root)
{
return TRUE;
}

bRet = IsBST(root->left, val);


if (bRet == TRUE)
{
if (root->data < (*val))
{
bRet = FALSE;
}
else
{
*val = root->data;
}
}

if (TRUE == bRet)
{
bRet = IsBST(root->right, val);
}

return bRet;
}

int min = minimum value of integer
int max = maximum value of integer
isBST(Tree node, min, max );

//actual method implementation
isBST(Tree node, int min, int max){

if(node==null)
return true;

if(node.value > min || node.value < max)
return false;

return isBST(node.left,min,node.data-1)&&isBST(node.right,node.data+1,max);

}

Do a INORDER trversal. You should get a sorted list.

/* C# Code */

 bool result = IsBST(root, MIN, MAX);

 private bool IsBST(TreeNode node, int min, int max)
        {
            if (node == null)
            {
                return true;
            }

            if (node.Value < min || node.Value > max)
            {
                return false;
            }

            Debug.WriteLine(string.Format("Current: {0} \t Left: {1} \t Right: {2}", node.Value, node.Left == null ? -1 : node.Left.Value, node.Right == null ? -1 : node.Right.Value));

            bool leftBST = false;
            bool rightBST = false;

            if (node.Left == null || node.Value > node.Left.Value)
            {
                leftBST = true;
            }

            if (node.Right == null || node.Value < node.Right.Value)
            {
                rightBST = true;
            }

            if (leftBST && rightBST)
            {
                return IsBST(node.Left, min, node.Value) && IsBST(node.Right, node.Value, max);
            }
            else
            {
                return false;
            }
        }

static class Node {
        public Node left;
        public Node right;
        public int data;
    }
public boolean isBst(Node node)
    {
        return isBinarySearchTree(node , Integer.MIN_VALUE , Integer.MAX_VALUE);
    }
    public boolean isBinarySearchTree(Node node , int min , int max)
    {
        if(node.data < min || node.data > max)
            return false;
        //Check this node!
        //This algorithm doesn't recurse with null Arguments.
        //When a null is found the method returns true;
        //Look and you will find out.
    /*
     * Checking for Left SubTree
     */
        boolean leftIsBst = false;
        //If the Left Node Exists
        if(node.left != null)
        {
            //and the Left Data are Smaller than the Node Data
            if(node.left.data < node.data)
            {
                //Check if the subtree is Valid as well
                leftIsBst = isBinarySearchTree(node.left , min , node.data);
            }else
            {
                //Else if the Left data are Bigger return false;
                leftIsBst = false;
            }
        }else //if the Left Node Doesn't Exist return true;
        {
            leftIsBst = true;
        }

    /*
     * Checking for Right SubTree - Similar Logic
     */
        boolean rightIsBst = false;
        //If the Right Node Exists
        if(node.right != null)
        {
            //and the Right Data are Bigger (or Equal) than the Node Data
            if(node.right.data >= node.data)
            {
                //Check if the subtree is Valid as well
                rightIsBst = isBinarySearchTree(node.right , node.data+1 , max);
            }else
            {
                //Else if the Right data are Smaller return false;
                rightIsBst = false;
            }
        }else //if the Right Node Doesn't Exist return true;
        {
            rightIsBst = true;
        }

        //if both are true then this means that subtrees are BST too
        return (leftIsBst && rightIsBst);
    }