Amazon Interview Question
SDE-2sCountry: India
Interview Type: In-Person
public boolean isValid(Node root) {
return isValidBST(root, Integer.MIN_VALUE,
Integer.MAX_VALUE);
}
private boolean isValidBST(Node node, int MIN, int MAX) {
if(node == null)
return true;
if(node.value > MIN
&& node.value < MAX
&& isValidBST(node.left, MIN, node.value)
&& isValidBST(node.right, node.value, MAX))
return true;
else
return false;
}
good one..
to optimize this solution we can have a global flag initialized with true will be set for any mismatch of below mentioned condition:
node.info > node.left.info
&&
node.info < node.right.info
in case of any mismatch set global flag to false and exit;
After execution of method in case flag is still true then binary tree is a BST
C++ version:
int isBST(struct node* node) {
return(checkIsBST(node, INT_MIN, INT_MAX));
}
int checkIsBST(struct node* node, int min, int max) {
if (node==NULL)
return true;
if (node->data<min || node->data>max)
return false;
return
( checkIsBST(node->left, min, node->data) &&
checkIsBST(node->right, node->data+1, max) );
}
The invariant for any single BST tree node is only these two conditions:
a) node.left.data <= node.data <= node.right.data
b) and recursively: isBST(node.left) and isBST(node.right) must be true.
A simple java solution is:
public boolean isBST(Node node) {
// Base cases
if (node == null) return true;
if (node.left != null && node.left.data > node.data) return false;
if (node.right != null && node.right.data < node.data) return false;
// recurse. If either or both of left and right subtree is null,
// it will handled by base-case above
return isBST(node.left) && isBST(node.right);
}
public boolean validBST(Node root)
{
if(root == null) return true;
return root.left.data < root.data && root.right.data>root.data && validBST(root.left) && validBST(root.right);
}
Add the child null case too in this please
Do inorder traversal of the tree if the inorder traversal is sorted then it is a BST otherwise not.
- khunima March 23, 2014