# Determine whether given binary tree is binary search tree(BST) or not

Objective: Given a Binary tree, find out whether its binary search tree or not.

Input: A Binary Tree.

Output: True or false based on whether tree is BST ot not.

Approach:

Method 1 : If tree doesn’t have duplicates

• Do the inorder traversal of the given binary tree.
• check if the previously visited node is less than the current node value.
• If yes, then return true
• Else return false.

The above method works only when tree doesn’t have any duplicates.(we can choose that ether duplicates will either go to left OR on the right but we cannot choose it randomly while constructing the tree, we need to decide before we construct the tree and it has to be consistent through out and here we are deciding that duplicates should go to the left subtree.) see figure,

Method 2: The Max/Min Solution :

When we talk about binary search tree we talk about one property i.e leftChild.data <=root.data<rightChild, but checking alone this property at every node is not gonna work out, want to know why, see this example

Now in the above example you can see that when you validate the Node 40, 10<=40<50 so it will return true nad when you validate the Node 30, 5<=30<40, will return true but as you can see that this tree is not BST since 10 is smaller than 30 so it should be on the left of the 30. Actually all the nodes less than 30 should be on the left and all the nodes greater than 30 should be on the right.

How would you achieve that???

Your root value can have any value between -∞ to + ∞. When you validate the right child of 30, it can take any value between 30 and + ∞. When you validate the left child of 30, it can take any value between – ∞ and 30. likewsie when you validate the left child of 40, it can take any value between 30 and 40.

So the idea is Pass the minimum and maximum values between which the node’s value must lie.

we start with the range minimum = Integer.MIN_VALUE and maximum = Interger.MAX_VALUE, so when checking the left node of 30(root), minimum will be = Integer.MIN_VALUE and maximum = 30, so on. See the figure for better understanding.

Complete Code for Both the methods:

 public class isBST { public static Node prevNode = null; // method 1: do inOrder and check if it is in ascending order // doesnt work in case of duplicates public boolean isBST1(Node root) { if (root != null) { if (!isBST1(root.left)) return false; if (prevNode != null && prevNode.data >= root.data) { return false; } prevNode = root; return isBST1(root.right); } return true; } // //method 2 // The max-Min solution public boolean isBST2(Node root, int min, int max) { if (root != null) { if (root.data > max || root.data < min) { return false; } return isBST2(root.left, min, root.data) && isBST2(root.right, root.data, max); } else { return true; } } public void inorder(Node root) { if (root != null) { inorder(root.left); System.out.print(" " + root.data); inorder(root.right); } } public static void main(String args[]) { isBST i = new isBST(); Node root = new Node(20); root.left = new Node(10); root.right = new Node(30); root.left.left = new Node(5); root.left.right = new Node(15); root.right.left = new Node(25); root.right.right = new Node(35); System.out.println("Tree is "); i.inorder(root); System.out.println(); System.out.println("is Tree BST ?? METHOD 1 : " + i.isBST1(root)); System.out.println("is Tree BST ?? METHOD 2 : " + i.isBST2(root, Integer.MIN_VALUE, Integer.MAX_VALUE)); root.left.right.right = new Node(40); System.out.println("Tree is "); i.inorder(root); System.out.println(); System.out.println("is Tree BST ?? METHOD 1 : " + i.isBST1(root)); System.out.println("is Tree BST ?? METHOD 2 : " + i.isBST2(root, Integer.MIN_VALUE, Integer.MAX_VALUE)); } } class Node { int data; Node left; Node right; public Node(int data) { this.data = data; left = null; right = null; } }

view raw
isBST.java
hosted with ❤ by GitHub

Output :

```Tree is
5 10 15 20 25 30 35
is Tree BST ?? METHOD 1 : true
is Tree BST ?? METHOD 2 : true
Tree is
5 10 15 40 20 25 30 35
is Tree BST ?? METHOD 1 : false
is Tree BST ?? METHOD 2 : false
```