Write an algorithm to see if a tree is a BST.

Question

Jordan · Accepted Answer

The above wont work, consider a tree that has a root value for 5, left is 4, right is 6, left of the left is 3 and right of the left is 6. This one should work (for integers):

boolean isBST(Node root) {
    return isBST_helper(root, INT_MIN, INT_MAX);
}

boolean isBST_helper(Node root, int min, int max) {
    if (root == null)
        return true;
    return root.value >= min && root.value < max &&
        isBST(root.left, min, root.value) && isBST(root.right, root.value+1, max);       
}

Naresh · Answer

public boolean checkBst(Node n) {
       if (n == null) return true;
       if (checkBst(n.left)) {
          if ( checkBst(n.right)) {
                      boolean isBst = false;
                      if (n.left != null){
                           isBst = n.left.data  n.data;
                      }
                      return isBst; 
          }
        }
        return false;  
}

Naresh · Answer

A mistake below corrected..
public boolean checkBst(Node n) {
       if (n == null) return true;
       if (checkBst(n.left)) {
          if ( checkBst(n.right)) {
                      boolean isBst = true;
                      if (n.left != null){
                           isBst = n.left.data  n.data;
                      }
                      return isBst; 
          }
        }
        return false;  
}

Naresh · Answer

What Jordan is saying is correct. We need to maintain bound for left and right subtrees.
The bound for left is min and root.value and for right is root.value and max. The above give n by me in incorrect. The correct on lines of Jordan -

    public static boolean isBST(Node t, int min, int max) {
        if (t == null) {
           return true;
        }
        if (isBST(t.left, min, t.value) && 
                isBST(t.right, t.value, max)) {
           boolean bst = true;
           if (t.left != null) {
               bst = (t.left.value >= min) && (t.left.value = min) && (t.right.value <= max);
           }
           return bst;
        }  else{
           return false;
        }
    }

Sigiloso · Answer

isBST(Node root)
	if root == null
		return false
	return isBST(root, root.value, true) && isBST(root, root.value, false)

isBST(Node root, Int root_value, Boolean left)
	
	if root == null
		return true
	
	if left == false ? rot.value = root_value && (root.left == null || root.left.value <= root.value) && (root.right == null || root.value < root.right.value)
			return true && isBST(root.left, root_value, left) && isBST(root.right, root_value, left)

	return false

Sigiloso · Answer

It is as if the simple solution above didn't detect correctly following case:

          2
     1         3
 0.    4

PixelPerfect3 · Answer

isBST(Node node):
    if node == null:               // no node is technically a bst tree
          return true;
    if node.left != null:
          if node.value  node.right:
              return false;
    
    return isBST(node.left) && isBST(node.right);


test:

isBST(tree.root)

Amazon

Pergunta de entrevista da empresa Amazon

Respostas da entrevista

Empresas seguidas

Buscas de vagas