A program written in C language to check whether a binary tree is a Binary Search Tree (BST)

Binary tree is a tree data structure, each node has two child nodes. These two child nodes are called left child node and right child node.

Binary search tree (BST) is a tree structure in which the left subtree contains nodes with a value less than the root node and the right subtree contains nodes with a value greater than the root node.

Here, we will check if a binary tree is BST:

In order to check this, we need to check the BST condition on the binary tree. For the root node, the value of the left child node should be less than the value of the root node, and the value of the right child node should be greater than the value of the root node. This condition must be met for all nodes with child nodes in the tree.

Program to check whether a binary tree is a BST

#include<bits/stdc++.h>
#include<iostream>
using namespace std;
class node {
   public:
      int data;
   node* left;
   node* right;
   node(int data) {
      this->data = data;
      this->left = NULL;
      this->right = NULL;
   }
};
int isBSTUtil(node* node, int min, int max);
int isBST(node* node) {
   return(isBSTUtil(node, INT_MIN, INT_MAX));
}
int isBSTUtil(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);
}
int main() {
   node *root = new node(8);
   root->left = new node(3);
   root->right = new node(10);
   root->left->left = new node(1);
   root->left->right = new node(6);
   if(isBST(root))
      cout<<"The given tree is a BST";
   else
      cout<<"The given tree is Not a BST";
   return 0;
}

Output

The given tree is a BST

Code explanation

The above code checks a binary search Tree. The main method creates a tree and calls the isBST() method. This method checks whether the left and right child nodes follow the binary search tree rules, and uses the isBSTuntil() method to check whether the formed subtree is also a binary search tree.

The above is the detailed content of A program written in C language to check whether a binary tree is a Binary Search Tree (BST). For more information, please follow other related articles on the PHP Chinese website!