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,

IsBST - Invald example

IsBST – Invald example

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

Invalid BST

Invalid BST

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.

IsBST Min-Max Solution

IsBST Min-Max Solution

Complete Code for Both the methods:

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

__________________________________________________
Top Companies Interview Questions..-

Google Microsoft Amazon Facebook more..

If you find anything incorrect or you feel that there is any better approach to solve the above problem, please write comment.
__________________________________________________

  • pavanprakash17

    A binary search tree (BST) is a tree in which all nodes follows the below mentioned properties −

    The left sub-tree of a node has key less than or equal to its parent node’s key.

    The right sub-tree of a node has key greater than or equal to its parent node’s key.
    duplicates can exist in method1 example it is also binary searchtree

    • tutorialhorizon

      Hi pavan,

      The point we are making here is that 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. I agree that article is has some confusion in it. Will correct it. Thanks for finding it out.

%d bloggers like this: