Check if tree is BST or not

Tags: , , , ,

Check if binary tree is (BST) or not

This is one of the most asked programming interview questions. How to check or validate that a given binary tree is BST or not or if a given tree is binary search tree? For example, first and second binary trees are BST but not the third one.

binary tree is BST or not
binary tree is BST

binary tree is BST or not
binary tree is BST
binary tree is bst or not
binary tree is not BST

In binary tree introduction  we touched upon the topic of recursive structure of binary search tree.  The first property to satisfy to be qualified as BST is: value in all nodes on the left subtree of the root node are smaller and value of all nodes in right subtree are greater than the root node. This property should be valid at all nodes.

Check if binary tree is (BST) or not: Recursive implementation

So, to see if the binary tree rooted a particular node is BST, the root is greater than all nodes on left subtree and less than all nodes on the right subtree. However, is it sufficient condition? Let’s take a counterexample and prove that even root is greater than all nodes on the left side and smaller than all nodes on right subtree, a binary tree may not be binary search tree. Look at the tree below.

In this tree above condition is satisfied, but we cannot call this binary tree a BST.

This is a recursive structure of binary search tree plays an important role. For a binary tree root at a node to be BST, it’s left subtree and right subtree should also be BST. So, there are three conditions which should be satisfied:

  1. Left subtree is BST
  2. Right subtree is BST
  3. Value of root node is greater than max in left subtree and less than minimum in right subtree

Check if binary tree is (BST) or not  : Recursive implementation

#include<stdio.h>
#include<stdlib.h>

#define true 1
#define false 0

struct node{
	int value;
	struct node *left;
	struct node *right;
};

typedef struct node Node;

Node * findMaximum(Node * root){
	if( !root ) return root;
	while( root->right ){
		root = root->right;
	}
	return root;
}

Node * findMinimum(Node * root){
	if( !root ) return root;
	while( root->left ){
		root = root->left;
	}
	return root;
}

int isBST(Node * node){

  	if(!node)
  		return true;
    
    if( ! ( node->left || node->right ) ) return true;   
  	int isLeft  = isBST(node->left);
  	int isRight = isBST(node->right);

  	if(isLeft && isRight){
  		/* Since we already know that left sub tree and
 		right sub tree are Binary search tree, finding min and max in them would be easy */
   	
   		Node *max  =  NULL;
   		Node *min  =  NULL;
   		if( node->left )
   			max = findMaximum(node->left);
   		if( node->right )
   			min = findMinimum(node->right);

   		//Case 1 : only left sub tree is there
    	if(max && !min)
        	return node->value > max->value;
   		//Case 2 : Only right sub tree is there
    	if(!max && min)
       		return node->value < min->value;
   		//Case 3 : Both left and right sub tree are there
    	return (node->value > max->value && node->value < min->value);
   }
   return false;
}

Node * createNode(int value){
  Node *newNode =  (Node *)malloc(sizeof(Node));
  
  newNode->value = value;
  newNode->right= NULL;
  newNode->left = NULL;
  
  return newNode;
}

Node * addNode(Node *node, int value){
  if(node == NULL){
      return createNode(value);
  }
  else{
     if (node->value < value){
        node->left = addNode(node->left, value);
      }
      else{
        node->right = addNode(node->right, value);
      }
  }
  return node;
}
 
/* Driver program for the function written above */
int main(){
  Node *root = NULL;
  //Creating a binary tree
  root = addNode(root,30);
  root = addNode(root,20);
  root = addNode(root,15);
  root = addNode(root,25);
  root = addNode(root,40);
  root = addNode(root,37);
  root = addNode(root,45);
  
  printf("%s", isBST(root ) ? "Yes" : "No" );
  
  return 0;
}

Check if binary tree is (BST) or not  : Optimized implementation

Above implementation to check if the binary tree is binary search tree or not is correct but inefficient because, for every node,  its left and right subtree are scanned to find min and max. It makes implementation non-linear.

How can we avoid re-scanning of left and right subtrees? If we can keep track max on left subtree and min on right subtree while checking those subtrees for BST property and use same min and max.

Start with INTEGER_MAX and INTEGER_MIN, check if the root node is greater than max and less than min. If yes, then go down left subtree with max changed to root value, and go down to right subtree with min changed to root value. It is a similar implementation as above, except from revisiting nodes.

#include<stdio.h>
#include<stdlib.h>

#define true 1
#define false 0
#define INT_MIN -32999
#define INT_MAX 32999

struct node{
	int value;
	struct node *left;
	struct node *right;
};

typedef struct node Node;

int isBSTHelper(Node *root, int max, int min){
    if(!root) return true;

    if(root->value < min || root->value > max){
        return false;
    }

    return isBSTHelper(root->left, root->value, min) &&
           isBSTHelper(root->right, max, root->value);
}

int isBST(Node *root){
    return isBSTHelper(root, INT_MAX, INT_MIN);
}


Node * createNode(int value){
  Node *newNode =  (Node *)malloc(sizeof(Node));
  
  newNode->value = value;
  newNode->right= NULL;
  newNode->left = NULL;
  
  return newNode;
}

Node * addNode(Node *node, int value){
  if(node == NULL){
      return createNode(value);
  }
  else{
     if (node->value < value){
        node->left = addNode(node->left, value);
      }
      else{
        node->right = addNode(node->right, value);
      }
  }
  return node;
}
 
/* Driver program for the function written above */
int main(){
  Node *root = NULL;
  //Creating a binary tree
  root = addNode(root,30);
  root = addNode(root,20);
  root = addNode(root,15);
  root = addNode(root,25);
  root = addNode(root,40);
  root = addNode(root,37);
  root = addNode(root,45);
  
  printf("%s", isBST(root ) ? "Yes" : "No" );
  
  return 0;
}

The complexity of the above implementation is O(n) as we are traversing each node only once.

Another method to see if the binary tree is BST or not is to do an inorder traversal of the binary tree and keep track of the previous node. As we know in order traversal of a binary search tree gives nodes in sorted order, previously visited node should be always smaller than the current node. If all nodes satisfy this property, a binary tree is a binary search tree. If this property is violated at any node, the tree is not a binary search tree.

The complexity of this implementation is also O(n) as we will be traversing each node only once

Please share if there is something missing or not correct. If you want to contribute and share your knowledge with thousands of learner around the world, please reach out to us at communications@algorithmsandme.com