Show Buttons
Share On Facebook
Share On Twitter
Share On Google Plus
Share On Linkdin
Share On Pinterest
Share On Reddit
Share On Stumbleupon
Contact us
Hide Buttons

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

Objec­tive: Given a Binary tree, find out whether its binary search tree or not.

Input: A Binary Tree.

Out­put: True or false based on whether tree is BST ot not.

Approach:

Method 1 : If tree doesn’t have duplicates

  • Do the inorder tra­ver­sal of the given binary tree.
  • check if the pre­vi­ously vis­ited node is less than the cur­rent 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 dupli­cates will either go to left OR on the right but we can­not choose it ran­domly while con­struct­ing the tree, we need to decide before we con­struct the tree and it has to be con­sis­tent through out and here we are decid­ing that dupli­cates should go to the left sub­tree.) see fig­ure,

IsBST - Invald example

IsBST — Invald example

Method 2: The Max/Min Solution :

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

Invalid BST

Invalid BST

Now in the above exam­ple you can see that when you val­i­date the Node 40, 10<=40<50 so it will return true nad when you val­i­date 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. Actu­ally 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 val­i­date the right child of 30, it can take any value between 30 and + ∞. When you val­i­date the left child of 30, it can take any value between — ∞ and 30. likewsie when you val­i­date the left child of 40, it can take any value between 30 and 40.

So the idea is Pass the min­i­mum and max­i­mum val­ues between which the node’s value must lie.

we start with the range min­i­mum = Integer.MIN_VALUE and max­i­mum = Interger.MAX_VALUE, so when check­ing the left node of 30(root), min­i­mum will be = Integer.MIN_VALUE and max­i­mum = 30, so on. See the fig­ure for bet­ter understanding.

IsBST Min-Max Solution

IsBST Min-Max Solution

Com­plete Code for Both the methods:

Out­put :

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

You may also like...

  • pavanprakash17

    A binary search tree (BST) is a tree in which all nodes fol­lows the below men­tioned properties −

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

    The right sub-tree of a node has key greater than or equal to its par­ent node’s key.
    dupli­cates can exist in method1 exam­ple it is also binary searchtree

    • tuto­ri­al­hori­zon

      Hi pavan,

      The point we are mak­ing here is that we can choose that ether dupli­cates will either go to left OR on the right but we can­not choose it ran­domly while con­struct­ing the tree, we need to decide before we con­struct the tree and it has to be con­sis­tent through out. I agree that arti­cle is has some con­fu­sion in it. Will cor­rect it. Thanks for find­ing it out.