CareerCup

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

/* 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;
	}

1) Take inorder traversal of BS tree.
2)Check if it is sorted in ascending order.

Following is the pseudocode:

Triplet {
	boolean isBST;	//The tree is BST or not
	int min;	//Minimum value in the tree
	int max;	//Maximum value in the tree
}

//check if subtree rooted at "root" is a BST
Triplet checkBST(Node root) {
	Triplet leftT, rightT;

	//IGNORING BOUNDARY CASES LIKE LEAVES ...
	leftT = checkBST(root.left);
	rightT = checkBST(root.right);

	//if both left and right subtrees are BSTs
	if(leftT.isBST && rightT.isBST) {
		//if this node is following the BST property then
		if(leftT.max<=root.key && root.key<=rightT.min)
			//the subtree rooted at this node is BST
			return new Triplet(true, leftT.min, rightT.max);
	}
	return new Triplet(false, leftT.min, rightT.max);	//not a BST
}

void check(sn *start){
sn * prev;
if(start != NULL){
prev = start;
check(start->left)
if(prev -> data > start -> data)
printf("The no = %d\n",start -> data);
else{
printf("It is not bst\n");
exit(0);
}
check(start -> right);
else
return;
}

Just apply the normal inorder traversal. As inorder gives us a sorted set of values so if at any time the given node's data is smaller than the previous node then the given node is not a bst

The following code is O(n). The concept is that if every node in the tree is a BST Node, then the tree is a BST. Basically if the node has a left or right child, you need to make sure
1) That the left child is smaller than it, and the right child is larger than it
2) that the left and right children are also binary search tree nodes

As soon as a condition doesn't apply you should return false. In the second if statement I could reduce some redundancy of only checking the left node if the right node was a BST node.

bool isBST(Node root)
{
	bool isBSNode = true;
	if (root == null)
		return isBSNode;
	if (root.Right != null)
	{
		if (root.Value >= root.Right.Value) 
			return false;
		isBSNode = isBSNode && isBST(root.Right);
	}
	if (root.Left != null)
	{
		if (root.Value <= root.Left.Value) 
			return false;
		isBSNode = isBSNode && isBST(root.Left);
	}
	return isBSNode;
}

private boolean isBSTAlternative(Node node, NodeHolder lastNode)
{
if (node == null)
return true;
if (isBSTAlternative(node.left, lastNode))
{
if (lastNode.node != null) {
if (lastNode.node.data > node.data)
return false;
}
lastNode.node = node;
return isBSTAlternative(node.right, lastNode);
}
return false;
}

bool checkBST(Node* p,int* depth)
{     
	if(p==NULL)
	{
		*depth=0;
		return true;
	}
	int left,right;
	if(checkBST(p->left,&left)&&checkBST(p->right,&right))
	{
		int temp=*left-*right;
		if(temp<-1||temp>1)
			return false;
		*depth=1+(*left>*right?*left:*right);
	}
	return true;
}

public boolean BST(Tree root){
boolean flag;
if(root.value){
return true;
} else if(root.getLeft().value<root.value && root.getRigth().value>root.value){
flag = BST (root.getLeft());
if(flag==true){
flag = BST(root.getRigth());
} else {
return flag;
}
} else {
return false;
}
return flag;
}

public boolean BST(Tree root){
		 boolean flag;
		if(root.value){
			return true;
		} else if(root.getLeft().value<root.value && root.getRigth().value>root.value){
			flag = BST (root.getLeft());
			if(flag==true){
				flag = BST(root.getRigth());
			} else {
				return flag;
			}
		} else {
			return false;			
		}
		return flag;
	}

java:

public boolean isBST(TreeNode root){
return isBST(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
}
isBST(TreeNode root, int min, int max){
if(root==null)
return true;
if(root.val>=min&&root.val<max){
return isBST(root.left, min, root.val)&&isBST(root.right, root.val, max);
}
else return false;
}

Correct solution is
1) root.data >= root-->left.data and root.data >= Max(root-->left) and root--left is BST
2) root.data <= root-->right.data and root.data <= Min(root-->right) and root-->right is BST

public boolean isBST(BinaryNode node)
	{
		boolean isBst = true;
		if (node == null)
		{
			return true;
		}
		
		if(node.left != null)
		{
			isBst = (node.data >= node.left.data) && (node.data >= max(node.left).data) && (isBST(node.left));
		}
		
		if(isBst && node.right != null)
		{
			isBst = (node.data <= node.right.data) && (node.data <= min(node.right).data) && (isBST(node.right));
		}
		
		return isBst;

	}
	
public BinaryNode min(BinaryNode node)
	{
		if(node == null)
		{
			return node;
		}
		if (node.left == null)
		{
			return node;
		}
		else
		{
			return min(node.left);
		}
	}

	public BinaryNode max(BinaryNode node)
	{
		if (node.right == null)
		{
			return node;
		}
		else
		{
			return max(node.right);
		}
	}