How do you validate a binary search tree?

Question

I read on here of an exercise in interviews known as validating a binary search tree.

How exactly does this work? What would one be looking for in validating a binary search tree? I have written a basic search tree, but never heard of this concept.

Answer 1

Actually that is the mistake everybody does in an interview.

Leftchild must be checked against (minLimitof node,node.value)

Rightchild must be checked against (node.value,MaxLimit of node)

IsValidBST(root,-infinity,infinity);  bool IsValidBST(BinaryNode node, int MIN, int MAX)  {      if(node == null)          return true;      if(node.element > MIN           && node.element < MAX          && IsValidBST(node.left,MIN,node.element)          && IsValidBST(node.right,node.element,MAX))          return true;      else           return false; } 

Another solution (if space is not a constraint): Do an inorder traversal of the tree and store the node values in an array. If the array is in sorted order, its a valid BST otherwise not.