In a Binary Tree, each node can have at most two nodes. For a binary tree to be a binary search tree (BST), the data of
all the nodes in the left sub-tree of the root node should be less than or equals to the data of the root. The data of all the nodes
in the right subtree of the root node should be greater than the data of the root.
There are various ways to validate Binary Search Tree. One of the simple way is: The in-order traversal
of a binary search tree results natural order. So, we can do in-order traversal and check for natural order. If the order sorted,
then it is binary search tree. We will give this implementation in the coming pages.
In this page we follow different approach. We will set min and max value for each node and validate node data
against min and max value. The same approach will continue for each left and right sub binary search tree in recursive way.
Here is the steps to validate binary search tree:
- Start with root node. In this case root node data min & max values can be extreme integer ranges. Pass min value as
Integer.MIN_VALUE and max value as Integer.MAX_VALUE.
- Make sure node data is falling under min & max values.
- Along with the above check, make sure the left and right sub trees are also go through similar checks.
- Make a recursive call on left node with no change in min value and node data as max value.
- Make a recursive call on right node with node data as min value and no change in max value.
- Check the the code for better understanding.
|