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

«
»
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. }

advertisement
$ 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
If you wish to look at all C++ Programming examples, go to C++ Programs.

advertisement
advertisement
advertisement
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He is Linux Kernel Developer & SAN Architect and is passionate about competency developments in these areas. He lives in Bangalore and delivers focused training sessions to IT professionals in Linux Kernel, Linux Debugging, Linux Device Drivers, Linux Networking, Linux Storage, Advanced C Programming, SAN Storage Technologies, SCSI Internals & Storage Protocols such as iSCSI & Fiber Channel. Stay connected with him @ LinkedIn