How do you validate a binary search tree?
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.
Solution 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.
Solution 2:
"Validating" a binary search tree means that you check that it does indeed have all smaller items on the left and large items on the right. Essentially, it's a check to see if a binary tree is a binary search tree.