Engineering Full Stack Apps with Java and JavaScript
For a BST, all left nodes should be less than or equal to current node and current node must be less than all right nodes.
We will have a recursive function that checks if this property is true for every node and all its sub trees:
If the method get null node, it may return true, and should be first checked (exit condition for the recursion).
Check if 'left nodes is less than or equal to current node and current node must be less than all right nodes.
Then call the method for subtrees and see if the follow the property of BST
checkIfBST(TNode n, int min, int max)
{
if(n==null)
return true;
if(n.data <=min || n.data > right)
return false;
boolean leftIsBST = checkIfBST(n.left, min, n.data);
if(!leftIsBST)
return false;
boolean rightIsBST = checkIfBST(n.right, n.data, max);
if(!rightIsBST)
return false;
return true;
}
The recursive function will be initially passed with the root node, Integer.MIN_VALUE and Integer.MAX_VALUE.
E.g. checkIfBST(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
Time complexity is O(N)
Space complexity is O(log N)