Hello all, today we will write a program to check if given Binary Tree is Binary Search Tree C++ or not. So let’s start with what properties a tree must satisfy so that it is a Binary Search Tree.
How to identify a Binary Search Tree:
The tree satisfies the binary search tree property, which states that the key in each node must be greater than or equal to any key stored in the left sub-tree, and less than or equal to any key stored in the right sub-tree.
Below is an example of Binary Search Tree:
How code works:
- Perform a simple inorder traversal and keep the previous value of the node.
- If the current node is smaller than the previous node then it is not a binary search tree
- Otherwise it is a Binary search Tree.
Checkout the program to implement Binary Search Tree C++
Program to check if Tree is Binary Search Tree C++:
#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; } 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; }
OUTPUT:
$ g++ binary_bst.cpp $ a.out The Given Binary Tree is a BST ------------------ (program exited with code: 1) Press return to continue
Comment below in case you want to discuss more about how to check if a given binary tree is a Binary Search Tree C++.
1 thought on “Program to check if Tree is Binary Search Tree C++”