Services
Technology Web App Development Mobile App Development Windows App Development Database Development UI/UX Development Cloud Development SEO Digital Marketing Guest Posting Content Writing Artificial Intelligence Data Science ERP Development CRM Development CMS Development LMS Development Business Listing Blockchain Technology Startup Promotion AI Tools Integration
Products
Data Converter Cleaner TUC - Unit Converter Import Export Survey Manager Tweet Controller
Developer
Article Blog Forum Interview Beginner News Startup Quiz
Users
Career
Apply Job Internship
Pricing
Login Sign Up Get a Quote

forum

home / developersection / forums / write a program to check if a given binary tree is a binary search tree.
Ask Question

Write a program to check if a given binary tree is a binary search tree.

Utpal Vishwas 608 21 Apr 2023

Write a program to check if a given binary tree is a binary search tree.

C Language data structureprograms
Updated 22 Apr 2023
Utpal Vishwas
Utpal Vishwas

Student

I am Utpal Vishwas from Uttar Pradesh. Have completed my B. Tech. course from MNNIT campus Prayagraj in 2022. I have good knowledge of computer networking.

Message

1 Answers

Aryan Kumar
Aryan Kumar 22 Apr 2023
Report Abuse 
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
// Define the binary tree node
struct TreeNode {
   int val;
   struct TreeNode* left;
   struct TreeNode* right;
};
// Function to create a new binary tree node
struct TreeNode* newNode(int data) {
   struct TreeNode* node = (struct TreeNode*) malloc(sizeof(struct TreeNode));
   node->val = data;
   node->left = NULL;
   node->right = NULL;
   return node;
}
// Function to check if a binary tree is a binary search tree
int isBSTUtil(struct TreeNode* node, int min, int max) {
   if (node == NULL) {
       return 1;
   }
   if (node->val < min || node->val > max) {
       return 0;
   }
   return (isBSTUtil(node->left, min, node->val - 1) && isBSTUtil(node->right, node->val + 1, max));
}
int isBST(struct TreeNode* root) {
   return isBSTUtil(root, INT_MIN, INT_MAX);
}
int main() {
   struct TreeNode* root = newNode(4);
   root->left = newNode(2);
   root->right = newNode(5);
   root->left->left = newNode(1);
   root->left->right = newNode(3);
   if (isBST(root)) {
       printf("The binary tree is a binary search tree.\n");
   } else {
       printf("The binary tree is not a binary search tree.\n");
   }
   return 0;
}

In this program, we define the binary tree node structure and a function to create a new binary tree node. We then define a recursive function isBSTUtil that takes a node, a minimum value, and a maximum value as arguments, and returns true if the tree rooted at the node is a binary search tree within the given range. We call this function initially with the root of the binary tree and the minimum and maximum possible integer values. The function returns true if the node is NULL (an empty tree) or if the node's value is within the given range and the left and right subtrees are also binary search trees within their respective ranges. We use INT_MIN and INT_MAX to represent the minimum and maximum integer values respectively.

Finally, we define another function isBST that calls isBSTUtil with the root of the binary tree and returns the result.

In the main function, we create a binary tree and call the isBST function to check if it is a binary search tree. We print the result accordingly.

MindStick Training