C++ Program to Check if a Tree is Binary Search Tree

«
»
This C++ program checks whether the nodes entered form a binary search tree, a tree consisting of only two child nodes.

Here is the source code of the C++ program to display whether the nodes given as input give a binary search tree as output or not. This C++ program is successfully compiled and run on DevCpp, a C++ compiler. The program output is given below.

  1. /*
  2.  * C++ Program To Check Whether a Given Tree is Binary Search Tree
  3.  */
  4. #include<stdio.h>
  5. #include<stdlib.h>
  6. #include<limits.h>
  7. #include<iostream>
  8. using namespace std;
  9. struct node
  10. {
  11.     int data;
  12.     struct node* left;
  13.     struct node* right;
  14. }*node1 = NULL;
  15. int isBSTUtil(struct node* node, int min, int max) 
  16. { 
  17.     if (node==NULL) 
  18.         return 1;      
  19.     if (node->data < min || node->data > max) 
  20.         return 0; 
  21.     return isBSTUtil(node->left, min, node->data-1) && isBSTUtil(node->right, node->data+1, max); 
  22. } 
  23. int isBST(struct node* node) 
  24. { 
  25.     return(isBSTUtil(node, INT_MIN, INT_MAX)); 
  26. } 
  27. struct node* newNode(int data)
  28. {
  29.     node1 = new node;
  30.     node1->data = data;
  31.     node1->left = NULL;
  32.     node1->right = NULL;
  33.     return(node);
  34. }
  35. int main()
  36. {
  37.     struct node *root = newNode(4);
  38.     root->left = newNode(2);
  39.     root->right = newNode(5);
  40.     root->left->left = newNode(1);
  41.     root->left->right = newNode(3); 
  42.  
  43.     if(isBST(root))
  44.         cout<<"Is BST";
  45.     else
  46.         cout<<"Not a BST";   
  47.     getch();
  48. }

Output
Is BST

Sanfoundry Global Education & Learning Series – 1000 C++ Programs.

Note: Join free Sanfoundry classes at Telegram or Youtube
advertisement
advertisement
If you wish to look at all C++ Programming examples, go to C++ Programs.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & technical discussions at Telegram SanfoundryClasses.