## Google Interview Question for Software Engineer / Developers

• -13

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

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

@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

Comment hidden because of low score. Click to expand.
0

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

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

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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

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

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

Is this really a Google question?

Comment hidden because of low score. Click to expand.
0

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

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

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

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

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

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

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

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.

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