## Amazon Interview Question for Testing / Quality Assurances

Comment hidden because of low score. Click to expand.
1
of 1 vote

bool isBST(Node* node){
if(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));
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

Boolean isBST(Tree* node)
{
if(node == NULL)
return true;
else if (node->left->data < node->data && node->right->data >= node->data)
return isBST(node->left) && isBST(node->right);
}

Of course u need checking to make sure u dont dereference a null pointer.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

simple: Do an inorder traversal (left, root, right) of the tree and if the values are in ascending order then the tree is a binary search tree.

Comment hidden because of low score. Click to expand.
0
of 0 vote

I htink SP's solution will work

Comment hidden because of low score. Click to expand.
0
of 0 vote

Nitu,

SP's solution will not work. It checks all {left, root, right } pairs in isolation. Consider this tree

4
/ 2 6
/ \ / 1 5 3 7

5 and 3 in wrong places (compare to 4) but SP's solution will still declare this as BST.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Nitu,

SP's solution will not work. It checks all {left, root, right } pairs in isolation. Consider this tree

4
/ 2 6
/ \ / 1 5 3 7

5 and 3 in wrong places (compare to 4) but SP's solution will still declare this as BST.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Nitu,

SP's solution will not work. It checks all {left, root, right } pairs in isolation. Consider this tree

4
/ 2 6
/ \ / 1 5 3 7

5 and 3 in wrong places (compare to 4) but SP's solution will still declare this as BST.

Comment hidden because of low score. Click to expand.
0
of 0 vote

sorry, the previous post's formatting was goofed up.
here's the tree:

______4
___2____6
__1_5__3_7

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

we cant do an inorder traversal of the tree and chk for the ascending values as a check fo the tree as - If we have many elements in the order of millions, then we would need an equally huge data structure like a stack or a linked list to store the numbers of the inorder traversal.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
1

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.