Google Interview Question for Software Engineer / Developers


Country: United States




Comment hidden because of low score. Click to expand.
3
of 5 vote

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:

public boolean isBST(Node root)  {
	return isBST(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
}

public boolean isBST(Node root, int min, int max) {
	if(root == null)
		return true;
	if(root.data <= min || root.data > max)
		return false;
	if(!isBST(root.left, min, root.data) || !isBST(root.right, root.data, max))
		return false;

	return true;
}

- Swapnil October 04, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

What if the BST is a generic collection? in that case you cannot use Integer max and min

- ??? October 08, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@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 October 16, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@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.

- Swapnil October 16, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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 October 04, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

@ 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.

- jx33wang October 04, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.....

- Anonymous October 04, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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;
}
}

- undefined October 05, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

- snigda October 05, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

bool isBST(TreeNode* root, int min_val = INT_MIN, int max_val = INT_MAX)
{
     if (root == NULL) return true;
     return root >= min_val && root <= max_val && isBST(root->left, min_val, root->val) && isBST(root->right, root->val, max_val); 
}

- fafdu1992 October 05, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Is this really a Google question?

- Anonymous October 07, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Why not? It is not as easy as you might be thinking. For instance, the answer given in question is completely wrong.

- Anonymous October 07, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

int isBST(struct bst *b)
{
static struct bst *prev=NULL;
if(b)
{
if(!isBST(b->lc))
  return 0;
if(prev!=NULL && b->data<=prev->data)
  return 0;
prev=b;
return isBST(b->rc);
}
}
return 1;

- Anonymous October 07, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
    }

- ??? October 08, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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
}

- pshaikh.jobs October 18, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Check if the inorder traversal of the tree is sorted or not..this should give the answer..

- AJ October 20, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

ತಮಲ್ಲಿಕಾರ್ಜುನ t

- Mallikarjuna t June 10, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

#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";
	}
}

- Rudra October 05, 2013 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More