Implement a function to validate whether a given binary tree is a BST (i.e. write an isBST() function).

Question

Utilisateur anonyme · Accepted Answer

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.

RK · Answer

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

Alexander · Answer

How come this function never returns true?

And why would you need min and max?

Anon · Answer

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

Anon · Answer

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

Rajagopal · Answer

// 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 value) return false;
		if(!ValidateImpl(currRoot->right, val)) return false;
	}
	return true;
}

Rajagopal · Answer

// 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 value) {
			if (!ValidateImpl(currRoot->left, leftMin, leftMax)) return false;
			if (leftMax != currRoot->left->value && currRoot->value 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  rightMax ? leftMax : rightMax;

	return true;
}

vittal · Answer

traverse in order and see if they r same

Utilisateur anonyme · Answer

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;
    }
}

Amazon

Question d’entretien chez Amazon

Réponses aux questions d'entretien

Entreprises suivies

Recherche d’emplois