Check whether the given Binary Tree is a Binary Search Tree(BST) or not

To find out given binary tree is a BST or not just check BST property recursively for each node. Below is function which will accomplish this.

static bool isItBinarySearchTree(treeNode *rootNode) {

	//if root node is null then its bst
	if (rootNode == NULL)
		return 1;
	//if rootNode left child value is gr8 then root node value
	if (rootNode->leftChild != NULL && rootNode->val < rootNode->leftChild->val)
		return 0;
	//if rootNode rightChild value is less then the root node value
	if (rootNode->rightChild != NULL
			&& rootNode->val > rootNode->rightChild->val)
		return 0;

	// check left and right children should also be bst
	if (!tree::isItBinarySearchTree(rootNode->leftChild)
			|| !tree::isItBinarySearchTree(rootNode->rightChild))
		return 0;

	//after traversing all nodes
	return 1;

}

But above function will give wrong result for below tree because we are just checking current node left and right children values.

let’s assume we have

     10
   /    \
   6      15
 /  \    /   \
5   19  12   18 

since we are checking current node left and right children values for node 6 left child value 5 witch is less then and right child value 19 is greater then, that is correct but 19 is greater then 10 which is violation of BST property.

To avoid above problem we have to check max value of left subTree and min value of right subTree with current node.

Here is function to check is binary tree is BST or not using min and max function.

 static bool isItBinarySearchTreeUsingMinAndMax(treeNode *rootNode) {

	//if rootNode is null means its BST
	if (rootNode == NULL)
		return 1;

	//if rootNode value is less then max value in left subtree
	if (rootNode->leftChild != NULL
			&& rootNode->val
					< tree::findMaxElementInTheBinaryTree(rootNode->leftChild))
		return 0;

	//if rootNode value is greater then min value in right subtree
	if (rootNode->rightChild != NULL
			&& rootNode->val
					> tree::findMinElementInTheBinaryTree(rootNode->rightChild))
		return 0;

	//check for left and right children
	if (!tree::isItBinarySearchTreeUsingMinAndMax(rootNode->leftChild)
			|| !tree::isItBinarySearchTreeUsingMinAndMax(rootNode->rightChild))
		return 0;

	// after checking all nodes
	return 1;
}
     

above function time complexity is O(n^2). we should do something for that
as we know In order traverse of a binary search tree is a shorted list so we can check each node value should greater then the previous node in InOrderTraversal.
Here is function with O(n) Time complexity.

 
static bool isItBinarySearchTreeUsingInOrderTraversal(treeNode *rootNode,
		int *min) {

	//if rootNode is null means it's BST
	if (rootNode == NULL)
		return 1;

	//check left child is BST or not
	if (!tree::isItBinarySearchTreeUsingInOrderTraversal(rootNode->leftChild,
			min))
		return 0;

	//check current node value if less then return 0
	if (rootNode->val < *min)
		return 0;

	//assign current node value to min
	*min = rootNode->val;

	//check right child is BST or not
	if (!tree::isItBinarySearchTreeUsingInOrderTraversal(rootNode->rightChild,
			min))
		return 0;

	return 1;
}

above mention function is member function of my Binary Search Tree ADT class you can check complete program here

A Developer
Gy@n!