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;
	}
TC - O(n2)
SC - O(n)

/* 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);
	}
TC - O(n)
SC - O(n)

Do inorder traversal, keep checking previously visited node is less then current node or not.
Please note, inorder traversal of binary tree prints data in sorted order.
Time Complexity: O(N), Space Complexity: O(N) for creating stack in recursive call.

Complexity O(n):
Code:

BinaryTreeNode prev=null;
	public boolean isBST(BinaryTreeNode root){
		if(root!=null){
			if(!isBST(root.left))
				return false;
			if(prev!=null && prev.data>root.data)
				return false;
			prev = root;
			return isBST(root.right);
		}
		return true;
	}

bool isBST(struct node* root)
{
      if(root==NULL)
      return true;

     if(root->data < min || root->data > max)      //min & max is minimum & maximum element.
     return false;

     else
     return isBST(root->lc,min,root->data) && isBST(root->rc,root->data+1,max)
}

struct min_max{
    int min;
    int max;
    int isBst;
}
typedef min_max MN

bool validateBst(Node *head)
{
    MN * ans = isBst(head);
    boo a =  ans->isBst;
    free(ans);
    return a;
}

MN * isBst(Node *head)
{
    if(head == NULL)
        return NULL;
      
    MN* left_mn = isBst(head->left);
    MN* right_mn = isBst(head->right);
    
    MN * ans = (MN *)malloc(size(MN));
    
    if(left_mn->isBst == 0 || right_mn->isBst == 0){
        ans->isBst = 0;
        free(left_mn);
        free(right_mn);
        return ans;
    }
    
    ans->min = left_mn==NULL? head->val: left_mn->min;
    ans->max = right_mn==NULL? head->val: right_mn->max;
    
    if(ans->isBst == 1 && left_mn->max <= head->val &&  head->val < right_mn->min )
        ans->isBst = 1;
    else
        ans->isBst = 0;
    
    free(left_mn);
    free(right_mn);
    return ans
}