Check if a Tree is a Binary Search Tree (BST) or Not

Let's start by understanding the problem statement for this task.

You are given a tree and your work is to check whether the given tree is BST or not.

Hint:

For checking if a tree is BST or not we have to take care that in the given tree the left subtree should be less than the data of root node and the right subtree must be greater than the data of root node, so for solving the above problem statement we initially have to use the c++ STL for INT_MIN and INT_MAX values in the range of integers and then keep updating it for traversing the left subtree and the right subtree.

Quick Think:

For checking if a given tree is a BST or not, we need to ponder over the following points and the conditions:-

• The condition should be that the node, if NULL then it is a BST.
• Any node in the tree should not be less than the value of INT_MIN and greater than the value of INT_MAX.
• The left subtree should be less than the data of the root node.
• The right subtree should be greater than the data of the root node.
• Keep updating the values of min and max while traversing the tree for the left subtree and the right subtree.

Algorithm:

Create a function with arguments as the reference of the root node, the INT_MIN, and the INT_MAX values and keep updating while traversing the left subtree and the right subtree and follow the steps below to reach the final output:-

Step1: Check for the condition that the current node is not NULL, if not then go to step 2 else return 1 because a NULL tree is a BST.

Step2: Check for the other condition that if the data of any node in the tree is less than the value of INT_MIN and greater than the value of INT_MAX then return 0 or -1 and terminate the algorithm.

Step3: Now recursively call the function and traverse the left subtree and keep checking for the data on the node and keep updating the max value to the value of node->data + 1.

Step4: Again, together call the recursive function and traverse the right subtree and keep checking for the data on the node and keep updating the min value to the value of node->data + 1.

Implementation Of The Above Algorithm:

Now let's see the implementation of the above algorithm,

#include <bits/stdc++.h>
using namespace std;
struct node
{
	int data;
	struct node *left, *right;
};

/*Function to add node to the tree. */
struct node* newnode(int data)
{
	struct node * node;
	node = (struct node *) malloc(sizeof(struct node));
	node->data = data;
	node->left = NULL;
	node->right = NULL;
	return node;
}

/*Function to find if a tree is BST or not. */
int istreeBST(struct node *node, int min, int max)
{
	if (node == NULL)
		return 1;
	if (node->data < min || node->data > max)
		return 0;
	return istreeBST(node->left, min, node->data + 1) && istreeBST(node->right, node->data + 1, max);
}

/*Driver program to test above functions. */
int main()
{
	struct node *root = newnode(4);
	root->left = newnode(1);
	root->right = newnode(5);
	root->left->left = newnode(0);
	root->left->right = newnode(8);

	if (istreeBST(root, INT_MIN, INT_MAX))
		cout << "Is BST" << endl;
	else
		cout << "Not a BST" << endl;
	return 0;
}

The time complexity of the above algorithm: O(n).

The output of the above algorithm: Not a BST.

Explanation Of The Above Algorithm:

Let us consider an example of the tree as shown in the diagram above and follow the steps below to reach the final output:-

• Pass the arguments to a function to check for BST as the pointer to the root node of the tree, the INT_MIN and the INT_MAX values.
• The root node is not NULL, so we move on to the next step.
• Now, the first root node’s data is not less than INT_MIN and not greater than the value of INT_MAX so we move to the next step.
• Now, simultaneously traverse the left and the right subtree with arguments as the reference to the node’s left subtree, the min value as INT_MIN and the max value as node->data + 1 for left subtree and for traversing the right subtree the arguments should be as the reference to the node’s right subtree, the min value as node->data + 1 and the max value as INT_MAX as shown in the above diagram.

• Now, we come to the left subtree, and we have the node with data 1 which is smaller than the root node data 4 and also the right subtree node with data 5 is greater than the root node data, hence the conditions are true, and we move to the next node in left subtree and the right subtree with arguments as node->left, min and 5 and node->right, 6 and max respectively as shown in the above diagram.

• Now, since the node with data 5 does not have a left subtree and neither a right subtree, so we move on to the left and the right subtree of the node with data 1 with arguments as node->left, min and 2 and node->right, 2 and max as shown in the above diagram.
• Now, finally the left and the right subtree of the nodes in the previous step does not exist, and we see, that the right child node of the node with data 1 is greater than the root data node hence, the given tree is not a BST.