Interview Question

Software Development Engineer Interview Seattle, WA

Implement a function to validate whether a given binary

  tree is a BST (i.e. write an isBST() function).
Tags:
Answer

Interview Answer

9 Answers

0

I came up with a recursive solution something like this:

boolean isBST(TreeNode node, int min = INT_MIN, int max = INT_MAX) {
    if (node != null) {
        if (node.left != null && node.left > max || node.right != null && node.right < min) {
             return false;
        }
        else {
             return (isBST(node.left, min, node.value) && isBST(node.right, node.value, max));
        }
    }
    else {
        return false;
    }
}

Interview Candidate on Feb 27, 2010
2

How come this function never returns true?

And why would you need min and max?

Alexander on Mar 10, 2010
6

Ok, so I should have spent a little more time posting this (I was admittedly rushing through it so I could get access to more questions/answers). Here's a revised version that should hopefully make more sense:

boolean isBST(TreeNode node, int min = INT_MIN, int max = INT_MAX) {
     if(node == null) {
         return true;
     }
     if(node.value > min &&
         node.value < max &&
         IsValidBST(node.left, min, node.value) &&
         IsValidBST(node.right, node.value, max)) {
         return true;
     }
     else {
         return false;
     }
}

The main change is that I decided to avoid checking the children of the tree in the body, and leave it to recursion to take care of that. Thus, we just have to look at the current "node" and that's it... the constraints will be handled by passing min and max down.

@Alexander - in response to your questions, the original function does in fact return true, if the condition (isBST(node.left, min, node.value) && isBST(node.right, node.value, max)) happens to evaluate to true. Finally, the min and max values are required because a BST requires that each value in the left branch be smaller than ALL parent values on that branch (and similarly for those on the right branch being larger). Another way of saying this is that the entire left tree of any node must be smaller than the node's value, and the entire right tree must be larger than the node's value. Thus, in a recursive solution, you have to have a way to pass down the upper and lower bounds to the lower levels of the tree, otherwise the third level won't be able to check whether it's smaller/larger than the root two levels up. That's why we pass down the min and max values.

Hope this helps.

Anonymous on Mar 11, 2010
1

boolean isBST(TreeNode node)
{
   if(node.isLeafNode( ))
      return true;
   else
   {
      if(node.value < node.leftChild || node.value > node.rightChild)
         return false;
      else
         return (isBST(node.leftChild) && isBST(node.rightChild))
   }
}

RK on Jul 28, 2010
0

traverse in order and see if they r same

vittal on Jul 31, 2010
1

@Alexander - in response to your questions, the original function does in fact return true, if the condition (isBST(node.left, min, node.value) && isBST(node.right, node.value, max)) happens to evaluate to true.
=============

Those are just two function calls and the function never returns true. Alexander is right - you are missing a terminating clause in your recursion.

Anon on Aug 24, 2010
1

Forgot to add - your second solution is correct since it returns true.

Anon on Aug 24, 2010
0

// For +ve number OR use INT_MIN instead of -1(s)
bool BinarySearchTree::validate() {
    int minVal = -1;
    int maxVal = -1;
    return ValidateImpl(root, minVal, maxVal);
}

bool BinarySearchTree::ValidateImpl(Node *currRoot, int &minVal, int &maxVal)
{
    int leftMin = -1;
    int leftMax = -1;
    int rightMin = -1;
    int rightMax = -1;

    if (currRoot == NULL) return true;

    if (currRoot->left) {
        if (currRoot->left->value < currRoot->value) {
            if (!ValidateImpl(currRoot->left, leftMin, leftMax)) return false;
            if (leftMax != currRoot->left->value && currRoot->value < leftMax) return false;
        }
        else
            return false;
    } else {
        leftMin = leftMax = currRoot->value;
    }

    if (currRoot->right) {
        if (currRoot->right->value > currRoot->value) {
            if(!ValidateImpl(currRoot->right, rightMin, rightMax)) return false;
            if (rightMin != currRoot->right->value && currRoot->value > rightMin) return false;
        }
        else return false;
    } else {
        rightMin = rightMax = currRoot->value;
    }

    minVal = leftMin < rightMin ? leftMin : rightMin;
    maxVal = leftMax > rightMax ? leftMax : rightMax;

    return true;
}

Rajagopal on Feb 13, 2012
0

// using inorder traverse based Impl
bool BinarySearchTree::validate() {
    int val = -1;
    return ValidateImpl(root, val);
}

// inorder traverse based Impl
bool BinarySearchTree::ValidateImpl(Node *currRoot, int &val) {
    if (currRoot == NULL) return true;

    if (currRoot->left) {
        if (currRoot->left->value > currRoot->value) return false;
        if(!ValidateImpl(currRoot->left, val)) return false;
    }

    if (val > currRoot->value) return false;
    val = currRoot->value;

    if (currRoot->right) {
        if (currRoot->right->value < currRoot->value) return false;
        if(!ValidateImpl(currRoot->right, val)) return false;
    }
    return true;
}

Rajagopal on Feb 14, 2012

Add Answers or Comments

To comment on this question, Sign In with Facebook or Sign Up