## Amazon Interview Question

Testing / Quality AssurancesGood one ... traverse the tree in in-order fashion and each time compare value of current node with previous node.

Though special consideration required for ensuring values in the lest subtree can be less than or equal to parent while value in right can only be greater (and not equal to) parent.

The above method will not work. consider a tree like this

{root} = 1 {2,10} // 2 is left child, 10 is right child

{10} = 10 {3,11} // Even though locally the conditions stisfy, globally its not a BST. Here 3 < 10 but it is in the wrong side of the root.

Boolean isBST(Tree *node, int & minVal) {

if (node == NULL)

return true;

if (!isBST(node->left, minVal)

return false;

if (minVal > this->data)

return false;

minVal = this->data;

if (!isBST(node->right, minVal)

return false;

return true;

}

call this function as

int minVal = MIN_INT;

// pass minVal by reference

isBST(root, minVal);

//or whatever is the least possible value of data

From the link below:

cslibrary.stanford.edu/110/BinaryTrees.html#csoln

/*

Returns true if a binary tree is a binary search tree.

*/

int isBST(struct node* node) {

if (node==NULL) return(true);

// false if the max of the left is > than us

// (bug -- an earlier version had min/max backwards here)

if (node->left!=NULL && maxValue(node->left) > node->data)

return(false);

// false if the min of the right is <= than us

if (node->right!=NULL && minValue(node->right) <= node->data)

return(false);

// false if, recursively, the left or right is not a BST

if (!isBST(node->left) || !isBST(node->right))

return(false);

// passing all that, it's a BST

return(true);

}

I think inorder traversal will work and you don't need a huge DS to store all the numbers.Just maintain two variable & compare currently read variable from the tree with the previously read var,if currently read is always greater than the prev read till we read the entire tree, it is BST, otherwise not.

int isBinary(TNODE *root,int min,int max)

{

if(root==NULL)

return 1;

if(root->info<min || root->info>max)

return 0;

return isBinary(root->lchild,min,root->info) && isBinary(root->rchild,root->info,max);

}

int minValue(TNODE *root)

{

if(root->lchild==NULL)

return root->info;

return minValue(root->lchild);

}

int maxValue(TNODE *root)

{

if(root->rchild==NULL)

return root->info;

return maxValue(root->rchild);

}

it works i have compiled this

the code is in perl but works fine

```
sub isBST {
my ($tree) = @_;
return 1 unless($tree);
if ($tree->{LEFT}) {
if ($tree->{LEFT}->{VALUE} > $tree->{VALUE}) {
return 0;
}
}
if ($tree->{RIGTH}) {
if ($tree->{RIGTH}->{VALUE} < $tree->{VALUE}) {
return 0;
}
}
return isBST($tree->{LEFT}) && isBST($tree->{RIGHT});
}
```

bool isBST(Node* node){

- Fishing April 22, 2007if(node==NULL)

return TRUE;

else if(node->left->data>node->data || node->right->data<node->data)

return FALSE;

else return(isBST(node->left) && isBST(node->right));

}