Google Interview Question
Software Engineer / DevelopersCountry: United States
What if the BST is a generic collection? in that case you cannot use Integer max and min
@Swapnil: I don't really think min and max are needed...because we are checking from root and going towards leaf node...so if upper tree is a BST i.e. left child of parent is less than current root. and thus we just need to check if the childrens of child satisfy this property which would suffice for global BST requirement.
for e.g. is root-> left < root
and root->left->left < root->left
then we can be sure that root->left->left < root
same for right subtree also
@Nik: But how about the case of comparision between root->left->right and root. You can't say whether one entity will be greater or less than the other.
Below is the example:
12
/ \
8 15
/ \
7 10
\
9
In this case assume root = 8, and then (root->left->right) > root in this example which can be can not be true always.
No it wont work...coz ur only looking at the immediate childs...what if the down the tree the BST properties are violated??
The solution i had in mind was just do inorder traversal and see if the array result is sorted or not.....
if any body can provide a better solution????
@ Krar - how does sivaji8's code not work? You two are ultimately performing the same checks, except you visit the nodes in in-order whereas sivaji8 does it in pre-order.
10
5 15
1 12 11 22
i think his code checks only immediate childs thats why his code wouldnt flag an error for the 12 on the 3rd level coz with respect to 5 the 12 is in correct location but with respect the root its in a wrong position.....
Will this work
public void iBST(Node n){
if( n != null){
if(n.left < n && n.right > n){
return (isBST(n.left) && isBST(n.right));
}else if(n.left == null && n.right > n){
return true;
}else if(n.right > n && n.left == null){
return true;
}else if(n.left == null && n.right == null){
return true;
}else{
return false;
}
}else{
return false;
}
}
public static boolean isBST(TreeNode<Integer> root, int min, int max){
if(root==null)
return true;
if(root.key<min || root.key > max)
return false;
if((root.leftChild !=null && isBST(root.leftChild, min, root.key)==false) ||
(root.rightChild !=null && isBST(root.rightChild, root.key, max)==false))
{
return false;
}
return true;
}
Swapnil's answer runs correct only if the tree is an integer storing bst. here is another solution for generic types. seperated into functions for ease of understanding
public boolean isBST() {
if (head == null) return true;
T value = head.value;
return (isBSTLeft(head.getLeft(), value) && isBSTRight(head.getRight(), value));
}
private boolean isBSTRight(Node<T> node, T min) {
if (node == null) return true;
T nodeValue = node.getValue();
if (nodeValue.compareTo(min) <= 0) {
return false;
}
return isBSTLeft(node.getLeft(), nodeValue) && isBSTRight(node.getRight(), min);
}
private boolean isBSTLeft(Node<T> node, T max) {
if (node == null) return true;
T nodeValue = node.getValue();
if (nodeValue.compareTo(max) > 0) {
return false;
}
return isBSTLeft(node.getLeft(), max) && isBSTRight(node.getRight(), nodeValue);
}
Not sure why max is really needed.
bool isbst(node* root)
{
if( root )
{
// if BST property is violated
if( root->left && root->left->data > root->data ||
root->right && root->right->data < root->data )
return false;
// if BST property holds for tree rooted at "root" & also holds true for its subtrees
return ( isbst(root->left) && (root->right) )
}
// Empty tree is BST
return true
}
#include<iostream>
#include<climits>
using namespace std;
class TreeNode{
public:
TreeNode* left;
TreeNode* right;
int val;
TreeNode(int);
};
TreeNode::TreeNode( int value ) {
left = NULL;
right = NULL;
val = value;
}
void createTree(TreeNode* node){
TreeNode* h;
h = node;
h->left = new TreeNode(2);
h->right = new TreeNode(5);
h->left->left = new TreeNode(1);
h->left->right = new TreeNode(4);
h->right->left = new TreeNode(6);
h->right->right = new TreeNode(7);
}
int customInorderTraversal(TreeNode *rootnode){
int maxval;
if(rootnode != NULL){
maxval = rootnode->val;
int maxleft = maxval;
int maxright = maxval;
if(rootnode->left != NULL)
maxleft = customInorderTraversal(rootnode->left);
if(rootnode->right != NULL)
maxright = customInorderTraversal(rootnode->right);
if(maxleft == INT_MIN || maxright == INT_MIN){
return INT_MIN;
}else{
if(maxleft <= maxval && maxval <= maxright){
return maxright;
}else{
return INT_MIN;
}
}
}else{
return INT_MAX;
}
}
int main(){
TreeNode* rootnode = (TreeNode*) new TreeNode(3);
createTree(rootnode);
int ret = customInorderTraversal(rootnode);
if(ret == INT_MIN){
cout<<"\n Input Btree is not BST ";
}else if(ret == INT_MAX){
cout<<"\n Empty Tree";
}else{
cout<<"\n Input BTree is BST";
}
}
You need to maintain global min and global max so that you can compare that any value in left subtree is always less than global minimum and similarly any value in right subtree should be greater than global maximum. Using that concept:
- Swapnil October 04, 2013