Binary Search Trees: A program to check if a binary tree is BST or not

Problem Statement:

You are given a root node of a binary tree.

You need to find out if a binary tree is a BST or not.

Solution

BST will have below 2 properties:

The left subtree of a node contains only node with data less than the node’s data

The right subtree of a node contains only node with data greater than the node’s data.

If the tree satisfy the above conditions, then it is a BST else it is BT.

So for the solution we will take 2 variables that will hold min and max values. So when we traverse the tree, we keep track of min and max allowed values.

Solution in C++

#include<iostream>
#include<vector>
#include<string>

using namespace std;

struct node 
{ 
      int data; 
      node *left; 
      node *right; 

    node(int data)
    {
        this->data = data;
        this->left = this->right = nullptr;
    }
}; 
  
bool check_is_BST(node* node, int min, int max) 
{
   if (node == NULL)
      return true;
   if (node -> data < min)
      return false;
  if (node -> data > max)
      return false;
   return check_is_BST(node -> right, node -> data, max) && 
  check_is_BST(node -> left, min, node -> data);       
}


int main() 
{ 
    node *root = NULL; 
      
    root = new node(10); 
    root->left = new node(-2); 
    root->right = new node(6); 
    root->left->left = new node(8); 
    root->left->right = new node(-4); 
    root->right->left = new node(7); 
    root->right->right = new node(5); 

    int min = INT_MIN;
    int max = INT_MAX;
  
    if(check_is_BST(root, min, max)){
       cout<<"This binary tree is a BST."<<endl;
    }
    else{
       cout<<"This binary tree is not a BST."<<endl;
    }

    return 0; 
} 

Output:

This binary tree is not a BST.

 

 

 

 

Write a Comment

Leave a Comment

Your email address will not be published. Required fields are marked *