C++ Check if a binary tree is a BST or not














































C++ Check if a binary tree is a BST or not



Check if a binary tree is a BST or not

Problem Description: Given the root of a binary tree, check whether it is a binary search tree or not. Binary Search Trees follow the following properties:-

  • All nodes in the left subtree of a node have values less than the node's value
  • All nodes in the right subtree of a node have values greater than the node's value
  • Both left and right subtrees are also binary search trees

The left side Binary Tree is a BST whereas the Right side Binary Tree is not a BST

The trick is to write a utility helper function isBSTUtil(struct node* node, int min, int max) that traverses down the tree keeping track of the narrowing min and max allowed values as it goes, looking at each node only once. The initial values for min and max should be INT_MIN and INT_MAX - they narrow from there.

For example, The allowed ranges are denoted in square brackets near the node


Below is the implementation of the above approach:


CODE
//A program to check if a binary tree is BST or not
#include<iostream>
#include<limits.h> //for INT_MIN and INT_MAX
using namespace std;
/* A binary tree node has data, pointer to left child
and a pointer to right child */

struct Node
{

int data;
Node* left;
Node* right;
/*For Creating New Node*/
Node(
int val)
{
data = val;
left =
NULL;
right =
NULL;
}
};

/* Returns true if the given
tree is a BST and its values
are >= min and <= max. */

int isBSTUtil(Node* node, int min, int max)
{
if (node==NULL) //if root is 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);
}

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

int isBST(Node* rt)
{
return(isBSTUtil(rt, INT_MIN, INT_MAX));
}

/* DRIVER FUNCTION */
int main()
{
//Inserting the elements according to the Tree
Node* root =
new Node(10);
root->left =
new Node(6);
root->right =
new Node(13);
root->left->left =
new Node(1);
root->left->right =
new Node(8);
root->right->left =
new Node(11);
root->right->right =
new Node(14);

if(isBST(root))
cout<<"Is BST";
else
cout<<"Not a BST";

return 0;
}

OUTPUT
Is BST


More Articles of Shaik Ismail:

Name Views Likes
C++ Shutdown Using C++ Code 385 1
C++ Majority Element (LeetCode) 328 0
C++ Missing Number(LeetCode) 155 0
C++ Count set bits in an integer 551 0
C++ Power of Two Leetcode BitManipulation 446 0
C++ Single Number LeetCode Bit Manipulation 214 0
C++ Radix Sort 186 0
C++ Wave Sort 161 0
C++ Counting Sort 155 0
C++ DNF Algorithm for Sorting 0,1,2 320 0
C++ Merge Sort 157 0
C++ Quick Sort 232 0
C++ Insertion Sort 153 0
C++ Selection Sort 167 0
C++ Bubble Sort 204 0
C++ DFS for a Graph 182 0
C++ BFS in Graph 197 0
C++ Graph Representation (Adjacency list) 160 0
C++ Graph Representation 181 0
C++ Basics of Graph Data Structure 163 0
C++ Diameter of a Binary Tree 193 0
C++ Check if a binary tree is a BST or not 494 0
C++ Heap Sort 364 0
C++ Deletion in Heaps 380 0
C++ Insertion of Elements in Heap 157 0
C++ Basics of Heap Data Structure 152 0
C++ Deletion in AVL Trees 138 0
C++ AVL Rotations 238 0
C++ AVL Tree 144 0
C++ Deletion of Nodes in BST 495 0
C++ Kth Largest Element in BST 149 0
C++ Kth Smallest Element in BST 175 0
C++ Searching in BST 137 0
C++ Insertion of Nodes in BST 138 0
C++ Basics of BST Part - 1 337 0
C++ Binary Tree is a SumTree or Not 122 0
C++ Sum of all leaf nodes 126 0
C++ Identical Binary Trees 132 0
C++ Mirror Binary Tree 190 0
CPP Project or program to get six subjects marks of a student and then calculate its total, average and percentage and display them on the screen 145 0
C++ Lowest Common Ancestor 143 0
C++ Bottom View of a Binary Tree 183 0
C++ Top View of a Binary Tree 131 0
C++ Vertical Order Traversal of a Binary Tree 198 0
C++ Level Order Traversal of a Binary Tree 172 0
C++ Height of the Binary Tree (Code) 131 0
C++ Binary Tree Representation and Traversals (Code) 170 1
C++ Binary Tree 135 0
C++ Basics of Tree Data Structure PART - 2 147 0
Tree 134 1
Basics of Tree Data Structure PART - 1 98 0

Comments