## Ebay Interview Question

Software Engineer / Developers**Country:**United States

**Interview Type:**Phone Interview

Java:

```
public boolean isBST(Node Root)
{
if (Root == null)
return true;
if (Root.value < Root.left.value || Root.value >= Root.right.value)
return false;
else
return isBST(Root.left) && isBST(Root.right)
}
```

void main()

{

isBst(root, Int.min, Int.max);

}

bool isBst(Node *r, int min, int max)

{

if(r == null) return false;

if(r->data < min || r -> data >= max) return false;

bool l = true, r = true;

if(r -> left != null)

l = isBst(r->left, min, r->data);

if(r->right != null)

r = isBst (r->right, r->data, max);

return (l & r);

}

/**

Tests if a tree meets the conditions to be a

binary search tree (BST). Uses the efficient

recursive helper.

*/

public boolean isBST2() {

return( isBST2(root, Integer.MIN_VALUE, Integer.MAX_VALUE) );

}

/**

Efficient BST helper -- Given a node, and min and max values,

recurs down the tree to verify that it is a BST, and that all

its nodes are within the min..max range. Works in O(n) time --

visits each node only once.

*/

private boolean isBST2(Node node, int min, int max) {

if (node==null) {

return(true);

}

else {

// left should be in range min...node.data

boolean leftOk = isBST2(node.left, min, node.data);

// if the left is not ok, bail out

if (!leftOk) return(false);

// right should be in range node.data+1..max

boolean rightOk = isBST2(node.right, node.data+1, max);

return(rightOk);

}

}

- Vir Pratap Uttam May 05, 2015