C++ Program to Check if a Binary Tree is BST or Not

This C++ Program Checks if a Binary Tree is a Binary Search Tree.

Here is source code of the C++ Program to check if a Binary Tree is a BST. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

  1. /*
  2.  * C++ Program to Check if a Binary Tree is a BST 
  3.  */
  4. #include <iostream>
  5. #include <cstdlib>
  6. #include <climits>
  7. using namespace std;
  8.  
  9. /* 
  10.  * Node Declaration 
  11.  */
  12. struct node
  13. {
  14.     int data;
  15.     node* left;
  16.     node* right;
  17. };
  18.  
  19. int isBSTUtil(node* node, int min, int max);
  20.  
  21. /* 
  22.  * Returns true if the given tree is a binary search tree 
  23.  */
  24. int isBST(node* node)
  25. {
  26.     return(isBSTUtil(node, INT_MIN, INT_MAX));
  27. }
  28.  
  29. /* 
  30.  * Returns true if the given tree is a BST and its
  31.  * values are >= min and <= max. 
  32.  */
  33. int isBSTUtil(struct node* node, int min, int max)
  34. {
  35.     if (node==NULL)
  36.         return 1;
  37.     if (node->data < min || node->data > max)
  38.         return 0;
  39.     return isBSTUtil(node->left, min, node->data - 1) &&  
  40.             isBSTUtil(node->right, node->data + 1, max);
  41. }
  42.  
  43. /* 
  44.  * allocates a new node with the data and NULL left and right pointers. 
  45.  */
  46. node* newNode(int data)
  47. {
  48.     node* nod = new node;
  49.     nod->data = data;
  50.     nod->left = NULL;
  51.     nod->right = NULL;
  52.     return nod;
  53. }
  54.  
  55. /* 
  56.  * Main
  57.  */
  58. int main()
  59. {
  60.     node *root = newNode(4);
  61.     root->left = newNode(2);
  62.     root->right = newNode(5);
  63.     root->left->left = newNode(1);
  64.     root->left->right = newNode(3);
  65.     if (isBST(root))
  66.         cout<<"The Given Binary Tree is a BST"<<endl;
  67.     else
  68.         cout<<"The Given Binary Tree is not a BST"<<endl;
  69.     return 0;
  70. }

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

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

advertisement
advertisement
If you wish to look at all C++ Programming examples, go to C++ Programs.

If you find any mistake above, kindly email to [email protected]

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 & discussions at Telegram SanfoundryClasses.