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.
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:
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..-
If you find anything incorrect or you feel that there is any better approach to solve the above problem, please write comment.