Binary Search Tree Validity

Write a function to determine whether a given binary tree of distinct integers is a valid binary search tree.
Assume that each node contains a pointer to its left child, a pointer to its right child, and an integer, but not a pointer to its parent. 

Answer:Note that it's not enough to write a recursive function that just checks if the left and right nodes of each node
are less than and greater than the current node (and calls that recursively).You need to make sure that all the nodes of
the subtree starting at your current node are within the valid range of values allowed by the current node's ancestors.

Therefore you can solve this recursively by writing a helper function that accepts a current node, the smallest allowed
value,and the largest allowed value for that subtree.

An example of this is the following (inJava):


boolean isValid(Node root) {
       return isValidHelper(root, Integer.MIN_VALUE,
                                      Integer.MAX_VALUE);
}
boolean isValidHelper(Node curr, int min, int max) {
       if (curr.left != null) {
              if (curr.left.value < min ||
                        !isValidHelper(curr.left, min, curr.value))
                   return false;
       }
       if (curr.right != null) {
              if (curr.right.value > max ||
                        !isValidHelper(curr.right, curr.value, max))
                   return false;
       }
       return true;
}

The running time of this algorithm is O(n).


Method II :
We can check given tree is BST or not by simply doing the in order traversal. While doing inorder traversal,don't store the elements any where.Keep track of min element.If the node value is less than means it is not sorted.So we return false.

In the initial function call  isBST(node20,-256);//min value = -256

public static boolean isBST(BTreeNode root, int min) {
  if (root == null)
   return true;
  if (!isBST(root.left, min))
   return false;
  if (root.value > min) {
   min = root.value;
  } else
   return false;
  if (!isBST(root.right, min))
   return false;
  return true;
 }