Amazon Interview Question SDE-2s
Country: United States
Interview Type: In-Person
Yeah agreed. Cant think of anything better than O(n). Am surprised that Amazon would ask such basic question.
it becomes a little more interesting if you need to do it in O(0) additional space.
For that you need to bound the possible values as your traverse the tree:
bool isBST(node* n, int min=MIN_INT, int max=MAX_INT)
{
if(n==NULL)
return true;
if(n->value <= min && n->value >= max)
return false;
return isBST(n->left,min,n->value) && isBST(n->right, n->value, max);
}
public class IsTreeBST {
public static void main(String[] args) {
NodeIsTreeBST temp = new NodeIsTreeBST();
temp = temp.NodeIsTreeBST(6);
temp.left = temp.NodeIsTreeBST(5);
temp.left.left = temp.NodeIsTreeBST(3);
temp.left.left.right = temp.NodeIsTreeBST(20);
temp.right = temp.NodeIsTreeBST(33);
temp.right.left = temp.NodeIsTreeBST(20);
temp.right.right = temp.NodeIsTreeBST(50);
System.out.println(isBST(temp, Integer.MIN_VALUE, Integer.MAX_VALUE));
}
public static boolean isBST(NodeIsTreeBST node , int min , int max) {
if(node == null)
return true;
if(node.data < min || node.data>max)
return false;
if(!isBST(node.left, min, node.data-1) || !isBST(node.right, node.data+1, max))
return false;
return true;
}
}
class NodeIsTreeBST {
int data;
NodeIsTreeBST left;
NodeIsTreeBST right;
public NodeIsTreeBST NodeIsTreeBST(int data) {
NodeIsTreeBST temp = new NodeIsTreeBST();
temp.data = data;
temp.left = null;
temp.right = null;
return temp;
}
}
int testBst(struct tree * root)
{
if (NULL == root)
return 0;
else
{
if (!( (!root->left || root->left->key < root->key) && (!root->right || root->right->key > root->key ) ))
return 0;
testBst(root->left);
testBst(root->right);
}
return 1;
}
It's faster if you do it without recursion. The big O(n) remains the same, however. So does the memory of O(log n):
public boolean isBst(TreeNode root){
if(root == null){
return false;
}
Stack<TreeNode> workingSpace = new Stack<TreeNode>();
workingSpace.push(root);
while(!workingSpace.isEmpty(){
TreeNode node = workingSpace.pop();
if(node.left != null){
if(node.left.value > node.value){
return false;
}
workingSpace.push(node.left);
}
if(node.right != null){
if(node.right.value <= node.value){
return false;
}
workingSpace.push(node.right);
}
}
return true;
}
For success scenario, it is o(n), but in case if the given tree in not BST like either its left or right child branch has more number of levels, then we need to break the iteration and we can mention that this is not BST.
This can be done by calculating the level of the node by inorder, and once we reached the last leaf node, we can start calculating the total number of nodes that we are traversing from bottom to top, at any stage if it is against 2N -1 , then it is not BST
- Vir Pratap Uttam May 10, 2015private static boolean isBST(BSTNode root) { if (root == null) return true; if (root.getLeft() != null && findMax(root.getLeft()) > root.getData()) return false; if (root.getRight() != null && findMin(root.getRight()) < root.getData()) return false; if (!(isBST(root.getLeft())) || (!isBST(root.getRight()))) return false; return true; }