## Amazon Interview Question

Developer Program Engineers**Team:**Love Film

**Country:**UK

**Interview Type:**Phone Interview

```
BOOL IsBST(Node *Root)
{
If(NULL == Root) return TRUE;
int min = findMin(Root);
int max = findMax(Root);
return IsBST(Root, min-1, max+1);
}
BOOL IsBST(Node *Root, int MIN, int MAX)
{
If(NULL == Root) return TRUE;
return ( (Root->info > MIN) &&
(Root->info < MAX) &&
IsBST(Root->Left, MIN, Root->Info+1) &&
IsBST(Root->Right, Root->Info-1, MAX) );
}
```

I think this : "

IsBST(Root->Left, MIN, Root->Info+1) &&

IsBST(Root->Right, Root->Info-1, MAX) );"

Should be :

IsBST(Root->Left, MIN, Root->Info) &&

IsBST(Root->Right, Root->Info, MAX) );

Because BST doesn't allow for the nodes to have the same value.

What do you think?

```
bool isBST(struct node *node)
{
return( isBSTHelper(node, INT_MIN, INT_MAX));
}
bool isBSTHelper(struct node *node, int min, int max)
{
if( node == NULL)
return true;
if( node->data < min || node->data > max )
return false;
return ( isBST(node->left, min, node->data) &&
isBST(node->right, node->data, max));
}
```

boolean isBst(Node root){

if (root == null) return true;

else{

bool temp;

if(node->left != null && node->left->value < node->value)

temp = true;

if(node->right != null && node->right->value > node->value)

temp = true;

if(temp)

return isBst(node->left) && isBst(node->right) ;

else

return false;

}

}

/**correction**/

boolean isBst(Node root){

if (root == null) return true;

else{

bool temp = true;

if(node->left != null && node->left->value > node->value)

temp = false;

if(node->right != null && node->right->value < node->value)

temp = false;

if(temp)

return isBst(node->left) && isBst(node->right) ;

else

return false;

}

}

@anonymous: this is wrong since you are not comparing with the value of ancestor. Checking only with parent is not enough. Eg:

6

4 9

3 7

This algorithm does not work because you are not checking whether entire left-sub tree is lesser than the 'node->value' and entire right subtree is greater than the 'node->value'.

```
bool flag = true;
int max_encountered = NEGATIVE_INFINITY;
void checkInorder(Node root){
if(root == null) return;
if(!flag){
println("Not a BST");
}
if( flag && root.left != null)
checkInorder(root.left);
if( flag && root.data > max_encountered){
max_encountered = root.data
}else{
flag = false;
}
if( flag && root.right != null)
checkInorder(root.right);
}
```

Please disregard my previous comment. Following is the solution as I thought:

public Boolean IsBst(Node nd) {

return IsBstI(nd, int.MinVal, int.MaxVal;

}

public Boolean IsBstI(Node nd, int min, int max) {

if (node.left != null) {

if (node.left < min || !IsBst(node.left, min, node.val) {

return false;

}

}

if (node.right != null) {

if (node.right > max || !IsBst(node.right, node.val, max) {

return false;

}

}

return true;

}

IsValidBST(root,Integer.MIN_VALUE,Integer.MAX_VALUE);

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;

}

bool isBST(node* root)

{

bool isBst = true;

if (NULL == root)

return true;

if (root != NULL)

{

if (root->lchild != NULL && ((root->data) < (root->lchild->data))) {

isBst = false;

}

if (root->rchild != NULL && ((root->data) > (root->rchild->data))) {

isBst = false;

}

isBST(root->lchild);

isBST(root->rchild);

}

return isBst;

}

- Vir Pratap Uttam May 05, 2015