# Binary Search Tree Check

A Binary Tree is a non-linear data structure. It is called a binary tree because each node has a maximum of two children. These children are called left children and right children. For a binary tree to become BST, it has to satisfy the following properties:

C#-S: if-else condition
C#-S: if-else condition
• All nodes in the left subtree are smaller than the root node.
• All nodes in the right subtree are larger than the root node.
• The left and right subtrees must also be binary search trees.

## the Algorithm of Checking If Binary Tree Is Binary Search Tree

### Algorithm 1

In this approach, we check if the left subtree contains any element greater than the root’s value and whether the right subtree contains an element smaller than the root’s value by considering every node as the root of its subtree. To find the max and min element, we have to use two separate functions, `getMin()` and `getMax()`.

### `getMin()`

• ##### While `temp` has a `left`, do the following:
• Set `temp` as `temp->left`, i.e. move towards the left to find the smallest element.

### `getMax()`

• ##### While `temp` has a `right`, do the following:
• Set `temp` as `temp->right`, i.e. move towards the right to find the largest element.

### `isBST(root)`

• ##### Recursively check all nodes by calling `isBST(root->left)` and `isBST(root->right)`. If both recursive calls return true then the tree is BST, return true otherwise return false.

The above algorithm tells us if a tree is BST or not but is extremely slow. The function `getMin()` and `getMax()` has a worst-case time complexity of `O(n)` and they are called for `n` nodes making the total time complexity O(n2).

### Algorithm 2:

This algorithm improves on the previous algorithm by not doing repeated computations. The previous approach called `getMin()` and `getMax()` for every node. This approach improves on the above approach by keeping track of the minimum and maximum allowed values as we traverse through the nodes.

### `isBST(root, min, max)`

• ##### If both the recursive calls return `true` then the tree is BST, return `true`.

This algorithm’s time complexity is `O(n)`, which is a significant improvement over the previous method.

### Algorithm 3:

This algorithm avoids using `INT_MIN` and `INT_MAX` in the above algorithm by replacing them with two pointers, `l` and `r`.

### Algorithm 4:

The inorder traversal of the binary search tree returns elements in sorted order. We can use this property to check if a binary tree is BST. If all the elements in inorder traversal are not in ascending order, then the given tree is not a binary search tree.

## Implementation of the Algorithm of Checking Binary Tree Is Binary Search Tree

### Algorithm 1

``````#include <iostream>
using namespace std;

class Node {
public:
int data;
Node *left, *right;
Node(int x) {
this->data = x;
this->left = this->right = NULL;
}
};
int getMin(Node* root)
{
while (root->left) {
root = root->left;
}

return root->data;
}
int getMax(Node* root)
{
while (root->right) {
root = root->right;
}

return root->data;
}
bool isBST( Node* root)
{
if (root == NULL)
return true;

if (root->left != NULL && getMax(root->left) > root->data)
return false;

if (root->right != NULL && getMin(root->right) < root->data)
return false;

if (!isBST(root->left) || !isBST(root->right))
return false;

return true;
}
int main()
{
Node *root = new Node(6);
root -> left = new Node(3);
root -> right = new Node(9);
root -> left -> left = new Node(1);
root -> left -> right = new Node(5);
root -> right -> left = new Node(7);
root -> right -> right = new Node(11);
if (isBST(root)) {
cout << "This binary tree is a BST." << endl;
}
else {
cout << "This binary tree is not a BST." << endl;
}
return 0;
}
``````

### Algorithm 2

``````#include <iostream>
using namespace std;

class Node {
public:
int data;
Node *left, *right;
Node(int x) {
this->data = x;
this->left = this->right = NULL;
}
};
bool isBST(Node* root, int min, int max)
{
if (root == NULL)
return 1;
if (root->data < min || root->data > max)
return 0;

return
isBST(root->left, min, root->data - 1) &&
isBST(root->right, root->data + 1, max);
}

bool isBST( Node* root)
{
return isBST(root, INT_MIN, INT_MAX);
}
int main()
{
Node *root = new Node(6);
root -> left = new Node(3);
root -> right = new Node(9);
root -> left -> left = new Node(1);
root -> left -> right = new Node(5);
root -> right -> left = new Node(7);
root -> right -> right = new Node(11);
if (isBST(root)) {
cout << "This binary tree is a BST." << endl;
}
else {
cout << "This binary tree is not a BST." << endl;
}
return 0;
}
``````

### Algorithm 3

``````#include <iostream>
using namespace std;

class Node {
public:
int data;
Node *left, *right;
Node(int x) {
this->data = x;
this->left = this->right = NULL;
}
};
bool isBST(Node* root, Node* l, Node* r)
{

if (root == NULL)
return true;

if (l != NULL and root->data <= l->data)
return false;
if (r != NULL and root->data >= r->data)
return false;

return isBST(root->left, l, root) && isBST(root->right, root, r);
}
bool isBST( Node* root)
{
Node* l = NULL;
Node* r = NULL;
return isBST(root, l, r);
}
int main()
{
Node *root = new Node(6);
root -> left = new Node(3);
root -> right = new Node(9);
root -> left -> left = new Node(1);
root -> left -> right = new Node(5);
root -> right -> left = new Node(7);
root -> right -> right = new Node(11);
if (isBST(root)) {
cout << "This binary tree is a BST." << endl;
}
else {
cout << "This binary tree is not a BST." << endl;
}
return 0;
}
``````

### Algorithm 4

``````#include <iostream>
using namespace std;

class Node {
public:
int data;
Node *left, *right;
Node(int x) {
this->data = x;
this->left = this->right = NULL;
}
};
bool isBST(Node* root, int& prev)
{

if (!root) return true;

if (!isBST(root->left, prev))
return false;

if (root->data <= prev)
return false;
prev = root->data;

return isBST(root->right, prev);
}

bool isBST(Node* root)
{
int prev = INT_MIN;
return isBST(root, prev);
}
int main()
{
Node *root = new Node(6);
root -> left = new Node(3);
root -> right = new Node(9);
root -> left -> left = new Node(1);
root -> left -> right = new Node(5);
root -> right -> left = new Node(7);
root -> right -> right = new Node(11);
if (isBST(root)) {
cout << "This binary tree is a BST." << endl;
}
else {
cout << "This binary tree is not a BST." << endl;
}
return 0;
}
``````

## Complexity Analysis

### Time Complexity

• Average Case

To check whether the given binary tree is BST or not, we have to traverse all `n` nodes because a single node defying the properties will lead to the tree not being BST. Hence the time complexity is of the order of [Big Theta]: `O(n)`.

• Best Case

The best-case time complexity is of the order of `O(n)`. It is the same as average-case time complexity.

• Worst-Case

The worst-case time complexity is of the order of `O(n)`. It is the same as best-case time complexity.

### Space Complexity

The algorithm’s space complexity is `O(n)` due to the extra space required by recursion calls.

## Related Article - Data Structure

• Circular Doubly Linked List
• Circular Linked List
• Doubly Linked List
• Linked List Deletion
• ## Related Article - Binary Tree

• Circular Doubly Linked List
• Circular Linked List
• Doubly Linked List
• Linked List Deletion
• ## Related Article - Binary Search Tree

• Circular Doubly Linked List
• Circular Linked List
• Doubly Linked List
• Linked List Deletion