Program to check if Tree is Binary Search Tree C++

Hello all, today we will write a program to check if given Binary Tree is Binary Search Tree C++ or not. So let’s start with what properties a tree must satisfy so that it is a Binary Search Tree.

How to identify a Binary Search Tree:

The tree satisfies the binary search tree property, which states that the key in each node must be greater than or equal to any key stored in the left sub-tree, and less than or equal to any key stored in the right sub-tree.

Below is an example of Binary Search Tree:

binary search tree c++

 

How code works:

  • Perform a simple inorder traversal and keep the previous value of the node.
  • If the current node is smaller than the previous node then it is not a binary search tree
  • Otherwise it is a Binary search Tree.

Checkout the program to implement Binary Search Tree C++

Program to check if Tree is Binary Search Tree C++:

#include <iostream>
#include <cstdlib>
#include <climits>
using namespace std;

//Node Declaration 
struct node
{
    int data;
    node* left;
    node* right;
};

int isBSTUtil(node* node, int min, int max);

//Returns true if the given tree is a binary search tree 
int isBST(node* node)
{
    return(isBSTUtil(node, INT_MIN, INT_MAX));
}
 
// Returns true if the given tree is a BST and its values are >= min and <= max. 

int isBSTUtil(struct node* node, int min, int max)

{
    if (node==NULL)
        return 1;
    if (node->data < min || node->data > max)
        return 0;
    return isBSTUtil(node->left, min, node->data - 1) &&  
            isBSTUtil(node->right, node->data + 1, max);
}

// allocates a new node with the data and NULL left and right pointers. 

node* newNode(int data)
{
    node* nod = new node;
    nod->data = data;
    nod->left = NULL;
    nod->right = NULL;
    return nod;
}

int main()
{
    node *root = newNode(4);
    root->left = newNode(2);
    root->right = newNode(5);
    root->left->left = newNode(1);
    root->left->right = newNode(3);
    
    if (isBST(root))
        cout<<"The Given Binary Tree is a BST"<<endl;
    else
        cout<<"The Given Binary Tree is not a BST"<<endl;
    return 0;
}

 

OUTPUT:

$ g++ binary_bst.cpp
$ a.out
 
The Given Binary Tree is a BST
 
------------------
(program exited with code: 1)
Press return to continue

Comment below in case you want to discuss more about how to check if a given binary tree is a Binary Search Tree C++.

1 thought on “Program to check if Tree is Binary Search Tree C++”

Leave a Comment