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.

```
/*
```

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

```
 */
```
```
#include <iostream>
```
```
#include <cstdlib>
```
```
#include <climits>
```
```
using namespace std;
```
```
 
```
```
/* 
```
```
 * Node Declaration 
```
```
 */
```
```
struct node
```
```
{
```
```
    int data;
```
```
    node* left;
```
```
    node* right;
```
```
};
```
```
 
```

int isBSTUtil(node* node, int min, int max);

```
 
```
```
/* 
```

 * Returns true if the given tree is a binary search tree

```
 */
```
```
int isBST(node* node)
```
```
{
```

    return(isBSTUtil(node, INT_MIN, INT_MAX));

```
}
```
```
 
```
```
/* 
```

 * Returns true if the given tree is a BST and its

```
 * values are >= min and <= max. 
```
```
 */
```

int isBSTUtil(struct 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);

```
}
```
```
 
```
```
/* 
```

 * allocates a new node with the data and NULL left and right pointers.

```
 */
```
```
node* newNode(int data)
```
```
{
```
```
    node* nod = new node;
```
```
    nod->data = data;
```
```
    nod->left = NULL;
```
```
    nod->right = NULL;
```
```
    return nod;
```
```
}
```
```
 
```
```
/* 
```
```
 * Main
```
```
 */
```
```
int main()
```
```
{
```
```
    node *root = newNode(4);
```
```
    root->left = newNode(2);
```
```
    root->right = newNode(5);
```
```
    root->left->left = newNode(1);
```
```
    root->left->right = newNode(3);
```
```
    if (isBST(root))
```

        cout<<"The Given Binary Tree is a BST"<<endl;

```
    else
```

        cout<<"The Given Binary Tree is not a BST"<<endl;

```
    return 0;
```
```
}
```

$ 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.

Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!

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

« Prev - C++ Program to Implement Disjoint Set Data Structure

» Next - C++ Program to Check if a Tree is Binary Search Tree

Next Steps:

Get Free Certificate of Merit in Data Structure I
Participate in Data Structure I Certification Contest
Become a Top Ranker in Data Structure I
Take Data Structure I Tests
Chapterwise Practice Tests: Chapter 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
Chapterwise Mock Tests: Chapter 1, 2, 3, 4, 5, 6, 7, 8, 9, 10

Related Posts:

Practice Programming MCQs
Apply for Data Structure Internship
Practice Computer Science MCQs
Apply for Information Technology Internship
Buy Data Structure Books

Recommended Articles: