Home » Interview coding problems/challenges

# Check whether a Binary Tree is BST (Binary Search Tree) or not

Here, we are going to learn how to **check whether a give binary tree is a binary search tree (BST) or not**?

Submitted by Radib Kar, on November 25, 2018

**Description:**

This article describes **how to check whether a given tree is BST or not**? This problem came in coding round of Microsoft.

**Problem Statement:**

Given a binary tree check whether it is a binary search tree or not.

**Solution**

**Algorithm:**

From the definition of BST, it may seem that for a binary tree to be BST, it’s enough to check for each node if the node on its left is smaller & node on its right is greater. But this is actually the wrong approach since it will give wrong output for many test-cases.

The correct algorithm is to check for each node whether the maximum of the left subtree is lesser than the node & the minimum of the right subtree is greater than the node. This algorithm works perfect but not efficient in terms of time complexity.

Intuition says that the in-order traversal for the BST results in a sorted list of nodes and we use this in our algorithm.

1. SetprevtoINT_MIN. 2. From main function call checkBST(root, prev) //passing prev by reference to update it every time checkBST(root, &prev) 3. if(root==NULL) return 1; //null tree is BST 4. do in-order traversal and checking whether all tree node data is sorted or not if(!(checkBST(root->left,prev))) //check left subtree return 0; //root->data must be greater than prevsince BST results in //sorted list after in-order traversal. 5. if(root->data<prev) return 0; 6. prev=root->data; //update prev value 7. return checkBST(root->right,prev);//check right subtree

**Example 1:**

Clearly Example 1 is a binary search tree. We will check out further through our function.

**Example 2:**

Clearly Example 2 is not a binary tree. We will check out through our function.

### C++ class implementation for tree

// tree node is defined class tree{ public: int data; tree *left; tree *right; };

### C++ function checkBST for implementation

//passing reference of prev int checkBST(tree* root,int &prev){ //null tree is BST if(root==NULL) return 1; //doing inorder traversal and checking whether //all tree node data is sorted or not if(!(checkBST(root->left,prev))) return 0; if(root->data<prev) return 0; prev=root->data; //update prev value return checkBST(root->right,prev); }

### C++ implementation for creating tree nodes

// creating new node tree* newnode(int data) { tree* node = (tree*)malloc(sizeof(tree)); node->data = data; node->left = NULL; node->right = NULL; return(node); }

### Main driver function for example1

#include <bits/stdc++.h> using namespace std; int main() { //**same tree is builted as shown in example** int c,prev=INT_MIN;//prev initialized to INT_MIN cout<<"Tree is built like the example 1 aforesaid"<<endl; tree *root=newnode(8); root->left= newnode(3); root->right= newnode(10); root->right->right=newnode(14); root->right->right->left=newnode(13); root->left->left=newnode(1); root->left->right=newnode(6); root->left->right->left=newnode(4); root->left->right->right=newnode(7); cout<<"builting the binary tree like example 1......"<<endl; c=checkBST(root,prev); if(c) cout<<"This binary tree is binary search tree"<<endl; else cout<<"This is not a binary search tree"; return 0; }

### Main driver function for example2

#include <bits/stdc++.h> using namespace std; int main() { //**same tree is builted as shown in example** int c,prev=INT_MIN;//prev initialized to INT_MIN cout<<"Tree is built like the example 2 aforesaid"<<endl; tree *root=newnode(2); root->left= newnode(7); root->right= newnode(5); root->right->right=newnode(9); root->right->right->left=newnode(4); root->left->left=newnode(2); root->left->right=newnode(6); root->left->right->left=newnode(5); root->left->right->right=newnode(11); cout<<"builting the binary tree like example 2......"<<endl; c=checkBST(root,prev); if(c) cout<<"This binary tree is binary search tree"<<endl; else cout<<"This is not a binary search tree"; return 0; }

**Output 1**

Tree is built like the example 1 aforesaid builting the binary tree like example 1...... This binary tree is binary search tree

**Output 2**

Tree is built like the example 2 aforesaid builting the binary tree like example 2...... This is not a binary search tree

Comments and Discussions

**Ad:**
Are you a blogger? Join our Blogging forum.