This post is completed by 1 user

  • 1
 Add to List
Medium

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

Objective: Given a Binary tree, find out whether it's a binary search tree or not.

Input: A Binary Tree.

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

Approach:

Method 1: If the 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 the tree doesn't have any duplicates. (we can choose that either duplicate will either go to the 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

Also Read: