CareerCup

Check in-order traversal is sorted or not

private boolean isBST() {
        return isBST(root, null, null);
    }

  private boolean isBST(Node x, Key min, Key max) {
        if (x == null) return true;
        if (min != null && x.key.compareTo(min) <= 0) return false;
        if (max != null && x.key.compareTo(max) >= 0) return false;
        return isBST(x.left, min, x.key) && isBST(x.right, x.key, max);
    }

It is probably simple to don't check for a null everytime or any other flag but just provide the maximum and minimum numbers of the int.Max and int.Min

class Node 
{
	int data;
	Node left;
	Node right;
}

public bool IsBST(Node root)
{
	return IsBST(root, int.Max, int.Min);
}

private bool IsBSTCore(Node root, int min, int max)
{
	if(root == null)
	{
		return true;
	}

	// Assuming that values can be repeated on either right or left
	if(root.data < min || root.data > max)
	{
		return false;
	}
	
	return IsBST(root.left, min, root.data) && IsBST(result.right, root.data, max);
}

bool isBST(struct node* root)
{
static struct node *prev = NULL;

// traverse the tree in inorder fashion and keep track of prev node
if (root)
{
if (!isBST(root->left))
return false;

// Allows only distinct valued nodes
if (prev != NULL && root->data <= prev->data)
return false;

prev = root;

return isBST(root->right);
}

return true;
}