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.