Problem Statement:
You are given a root node of a binary tree.
You need to find out if a binary tree is a BST or not.
Solution
BST will have below 2 properties:
The left subtree of a node contains only node with data less than the node’s data
The right subtree of a node contains only node with data greater than the node’s data.
If the tree satisfy the above conditions, then it is a BST else it is BT.
So for the solution we will take 2 variables that will hold min and max values. So when we traverse the tree, we keep track of min and max allowed values.
Solution in C++
#include<iostream>
#include<vector>
#include<string>
using namespace std;
struct node
{
int data;
node *left;
node *right;
node(int data)
{
this->data = data;
this->left = this->right = nullptr;
}
};
bool check_is_BST(node* node, int min, int max)
{
if (node == NULL)
return true;
if (node -> data < min)
return false;
if (node -> data > max)
return false;
return check_is_BST(node -> right, node -> data, max) &&
check_is_BST(node -> left, min, node -> data);
}
int main()
{
node *root = NULL;
root = new node(10);
root->left = new node(-2);
root->right = new node(6);
root->left->left = new node(8);
root->left->right = new node(-4);
root->right->left = new node(7);
root->right->right = new node(5);
int min = INT_MIN;
int max = INT_MAX;
if(check_is_BST(root, min, max)){
cout<<"This binary tree is a BST."<<endl;
}
else{
cout<<"This binary tree is not a BST."<<endl;
}
return 0;
}
Output:
This binary tree is not a BST.