Binary Search Tree Check

  2. Tutorial
  3. Data Structure
  4. Binary Search Tree Check
Harshit Jindal Oct 12, 2023
Data Structure Binary Tree Binary Search Tree
  1. the Algorithm of Checking If Binary Tree Is Binary Search Tree
  2. Implementation of the Algorithm of Checking Binary Tree Is Binary Search Tree
  3. Complexity Analysis
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:

  • 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()

  • Initialize temp as root.
  • While temp has a left, do the following:
    • Set temp as temp->left, i.e. move towards the left to find the smallest element.
  • Return temp->val as the minimum value inside that subtree.

getMax()

  • Initialize temp as root.
  • While temp has a right, do the following:
    • Set temp as temp->right, i.e. move towards the right to find the largest element.
  • Return temp->val as the maximum value inside that subtree.

isBST(root)

  • If the root is NULL, return true.
  • Find maximum element maxm in the left subtree by calling getMax(root->left);
  • Find minimum element minm in the right subtree by calling getMin(root->right);
  • If the root element is smaller than maxm or greater than minm, return false.
  • 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)

  • Initialize two variables min as INT_MIN and max as INT_MAX.
  • Call isBST(root,min,max).

isBST(root, min, max)

  • If the root is NULL, return true.
  • If min > root->data then BST property is violated, return false.
  • If max < root->data then BST property is violated, return false.
  • Recursively check the left subtree by calling isBST(root->left, min, root->data-1) (passing min and root->data - 1 as arguments changes the valid range for BST in left subtree) and the right subtree by calling isBST(root->right, root->data+1, max) (passing root->data + 1 and max as arguments changes the valid range for BST in right subtree).
  • 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.

isBST(root)

  • Initialize two nodes l and r as NULL.
  • Call isBST(root, l, r). (Overloaded Function Call)

isBST(root, l, r)

  • If the root is NULL, return true.
  • If l is not NULL and l->data >= root->data then BST property is violated, return false.
  • If r is not NULL and r->data <= root->data then BST property is violated, return false.
  • Recursively check the left subtree by calling isBST(root->left, left, root) (passing root as 3rd argument changes the minimum value limit for subtree) and the right subtree by calling isBST(root->right, root, right) (passing root as 2nd argument changes the maximum value limit for subtree).
  • If both the recursive calls return true then the tree is BST, return true.

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.

isBST(root)

  • Initialize variable prev as INT_MIN. prev is used to check whether the current node is larger than prev and hence following the sorted order.
  • Call isBST(root, prev). (Overloaded function Call).

isBST(root,prev)

  • If the root is NULL, return true.
  • Recursively check left subtree by isBST(root->left, prev). If it returns false then return false.
  • If root->data <= prev. ascending order is violated , return false.
  • Update prev->data as root->data.
  • Recursively check right subtree by isBST(root->right, prev). If it returns false then return false.
  • Else return true.

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.

Author: Harshit Jindal
Harshit Jindal avatar Harshit Jindal avatar

Harshit Jindal has done his Bachelors in Computer Science Engineering(2021) from DTU. He has always been a problem solver and now turned that into his profession. Currently working at M365 Cloud Security team(Torus) on Cloud Security Services and Datacenter Buildout Automation.

LinkedIn

Related Article - Data Structure

Related Article - Binary Tree

Related Article - Binary Search Tree