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.

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

Related Posts:

Practice Design & Analysis of Algorithms MCQ
Practice Programming MCQs
Practice Computer Science MCQs
Check Data Structure Books
Apply for Computer Science Internship

Recommended Articles: