Part 1

Write a function that checks whether a given binary tree is a BST or not.

Consider the following simple program. For each node, check if the left node of it is smaller than the node and the right node is greater than the node. This approach is wrong as this will return true for the below binary tree. Checking only at current node is not enough.

int isBST(Btree tree)
{
     if(tree == NULL)
          return 1;

     /* false if left is > than root */
     if(tree->left != NULL && tree->left->data > tree->data)
          return 0;

     /* false if right is < than root */
     if(tree->right != NULL && tree->right->data < tree->data)
          return 0;

     /* false if, recursively, the left or right is not a BST */
     if(!isBST(tree->left) || !isBST(tree->right))
          return 0;

     /* passing all that, it's a BST */
     return 1;
}

Think of getting the correct algorithm.

Part 2

The following function checks whether a given binary tree dynamically implemented is a BST or not.
int isBST(Btree tree)
{
     if(tree == NULL) return 1;
     if(tree->left != NULL && FindMax(tree->left) > tree->data) return 0;
     if(tree->right != NULL && FindMin(tree->right) < tree->data) return 0;
     if(!isBST(tree->left) || !isBST(tree->right)) return 0;
     return 1;
}

\(FindMax\) and \(FindMin\) are 2 auxiliary functions that returns the maximum (resp. minimum) element of a \(BST\).

element FindMin(Btree tree)
{
     if (tree==NULL) return INT_MAX;
     return min(tree->data,min(FindMin(tree->left),FindMin(tree->right)));
}

element FindMax(Btree tree)
{
     if (tree==NULL) return INT_MIN;
     return max(tree->data,max(FindMax(tree->left),FindMax(tree->right)));
}

• Without performing calculation, give the worst-case time complexity of the \(isBST\) function. Justify your answer.
• Note that the inorder traversal of BSTs produces sorted lists. While traversing the BST in inorder, and at each node, check the condition that its key value should be greater then the key value of its previous visited node.
  Write a recursive function that checks whether a given binary tree is a BST or not given the above approach.
• Without performing calculation, give the worst-case time complexity of your function. Justify your answer.

Part 1

element FindMin(Btree tree)
{
	element res;
	int lres, rres;
    	if (tree == NULL)	return INT_MAX;

     	res = tree->data;
     	lres = FindMin(tree->left);
     	rres = FindMin(tree->right);
    	if (lres < res)
      		res = lres;
    	if (rres < res)
      		res = rres;
    	return res;
}

element FindMax(Btree tree)
{
	element res;
	int lres, rres;
	if (tree == NULL) return INT_MIN;
     	res = tree->data;
     	lres = FindMax(tree->left);
     	rres = FindMax(tree->right);
    	if (lres > res)
      		res = lres;
    	if (rres > res)
      		res = rres;
    	return res;
}

int isBSTC(Btree tree)
{
	 if(tree == NULL)
		 return 1;

	 if(tree->left != NULL && FindMax(tree->left) > tree->data)
		 return 0;

	 if(tree->right != NULL && FindMin(tree->right) < tree->data)
		 return 0;

	 if(!isBST(tree->left) || !isBST(tree->right)) 
		 return 0;

	 return 1;
}


Part 2

1.	O(N^2)

2.	
int isBST(Btree B, int *prev)
{
		if(!B) return 1;
		if(!isBST(B->left, prev)) return 0;
		if(B->data< * prev) return 0;
		*prev=B->data;
		return isBST(B->right,prev);
}

from Main 
int previous=INT_MIN;
printf("\n\n\nIsBST: %d \n\n\n", isBST(B,&previous));


3.	O(N)