What is validating 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.

Thanks

Answer 1

"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.

This page allows you to draw a binary tree and validate it to see if it's a binary search tree.

Answer 2

Consider this algorithm (C-Style pseudocode):

Assuming this BinaryNode data structure:

BinaryNode
{
  BinaryNode left;
  BinaryNode right;
  T element;
}



bool IsValidBST(BinaryNode node) 
{
  // If the (sub-)tree is empty (recursion ends) or a leaf node,
  // no problem.
  if (node == null || node.left == null && node.right == null)
    return true;

  // Or if node with either (left or right) child nodes or both children.
  else 
  {

    // Check the value of this/parent node against
    // that of the left child.  If left child is not present,
    // no problem.  If the left child does exist
    // and its element value is larger than this node's.
    // the BST property is not valid.

    if (node.left != null && (node.element < node.left.element))
      return false;

    // Now we test with the right child.
    if (node.right != null && (node.right.element < node.element))
      return false;

    // If the BST property at this node is satisfied,
    // then the rest is up to the conditions of the left and
    // right subtrees, both must return true from recursive calls.
    return IsValidBST(node.left) && IsValidBST(node.right);
  }
}

Answer 3

Hi,

Just as I expected. You are checking the values, recursively.

Answer 4

Given the following tree.

    10
   /  \
  5   20
     /  \
    6    21

Using the above algorithm, wouldn't IsValidBST return true for this tree? But, I don't this this is a valid binary search tree since 6 is less than 10.

Answer 5

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.

Answer 6

I used the code from g0na in an interview last week. I had gotten this exact question in a previous interview and looked up the the answer. The code is exactly what an interviewer is looking for: a simple, tight solution to a problem you'll likely never see in the real world. I still waiting for "how to tell if 2 rectangles overlap."

Answer 7

Here is my solution in Clojure:

(defstruct BST :val :left :right)

(defn in-order [bst]
  (when-let [{:keys [val, left, right]} bst]
    (lazy-seq
      (concat (in-order left) (list val) (in-order right)))))

(defn is-strictly-sorted? [col]
  (every?
    (fn [[a b]] (< a  b))
    (partition 2 1 col)))

(defn is-valid-BST [bst]
  (is-strictly-sorted? (in-order bst)))

Answer 8

It's better to define an invariant first. Here the invariant is -- any two sequential elements of the BST in the in-order traversal must be always less or equal (greater or equal). So solution can be just a simple in-order traversal with remembering the last visited node and comparison the current node against the last visited one to '<' (or '>').