VMWare Inc Interview Question
Member Technical StaffsCountry: India
Interview Type: In-Person
/* Check for binary tree whether its binary search tree */
private static boolean isBST(BSTNode root, int prev) {
if(root==null)
return true;
if(!isBST(root.getLeft(),prev))
return false;
if(root.getData()<prev)
return false;
prev=root.getData();
return isBST(root.getRight(),prev);
}
TC - O(n)
SC - O(n)
Do inorder traversal, keep checking previously visited node is less then current node or not.
Please note, inorder traversal of binary tree prints data in sorted order.
Time Complexity: O(N), Space Complexity: O(N) for creating stack in recursive call.
Providing code for the above approach
int prev = Integer.MIN_VALUE;
int current = 0;
boolean isValid = true;
public boolean validateBST (Node root){
isValidBST (root);
return isValid;
}
private boolean isValidBST (Node root) {
if (root == null) {return;}
isValidBST (root->left);
if (isValid){
current = root->value;
if (current > prev) {
prev = current;
}else{
isValid = false;
}
}
isValidBST (root->right);
}
struct min_max{
int min;
int max;
int isBst;
}
typedef min_max MN
bool validateBst(Node *head)
{
MN * ans = isBst(head);
boo a = ans->isBst;
free(ans);
return a;
}
MN * isBst(Node *head)
{
if(head == NULL)
return NULL;
MN* left_mn = isBst(head->left);
MN* right_mn = isBst(head->right);
MN * ans = (MN *)malloc(size(MN));
if(left_mn->isBst == 0 || right_mn->isBst == 0){
ans->isBst = 0;
free(left_mn);
free(right_mn);
return ans;
}
ans->min = left_mn==NULL? head->val: left_mn->min;
ans->max = right_mn==NULL? head->val: right_mn->max;
if(ans->isBst == 1 && left_mn->max <= head->val && head->val < right_mn->min )
ans->isBst = 1;
else
ans->isBst = 0;
free(left_mn);
free(right_mn);
return ans
}
- Vir Pratap Uttam May 05, 2015