Amazon Flipkart Groupon Interview Question for Software Engineer / Developers


Country: -
Interview Type: In-Person




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

Do an Inorder traversal of the tree and check if that is sorted. If in-order traversal is sorted then it is a BST

- vinaysachdeva23 October 13, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 votes

that's my solution... :)

- Sanjay Kumar October 15, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

int arr[10];
//7 element
void check(tree*root)
{
if(root->left!=NULL)
check(root->left);
arr[i++]=root->val;
if(root->right!=NULL)
check(root->right);


}



int main::
int found=0;
check(root)
for(int i=0;i<=7; i++)
{


cout<<"\n "<<arr[i];
if((arr[i]>arr[i+1])&&i!=7 )//7 element
found=1;
}
if (found==0)
cout<<"\nBINARY SEARCH TREE IT IS:SORTED";
else
cout<<"NOT A BINARY SEARCH TREE";
return 0;

- sahil April 22, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I given this solution where I am not qualified bad. Because it fails for some inputs.

- pirate September 14, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

What if the number of nodes are in billions, then doing inorder traversal is the worst method for this program #ask in amazon.

- Raj May 26, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Raj : If number of nodes is in billions, then checking this will take a lot of time whichever way you use, don't you think?

The inorder travesal will be a good way to use if the discrepancy is near the bottom of the tree; as it will return false as soon as it finds two nodes that are not in correct order. In the same case(discrepancy near the bottom of the tree), if you use the top-down recursive approach, it will be slower IMO. I think the efficiency an approach depends on where exactly the fault is - somewhere near the root of the tree, or near the deepest leaves..

- Abhishek Tamhane January 04, 2015 | Flag
Comment hidden because of low score. Click to expand.
4
of 4 vote

It's a mix of c and pseudo code. The only problem is if the first element(root) is equal to MIN_INT. An extra if statement can overcome that condition but I think this should work otherwise.

1 int checkbst(struct node *root, int min, int max)
  2 {
  3         if(root == NULL)
  4                 return 1;
  5 
  6         return ( (root->data >min && root->data <= max) && checkbst(root->le    ft,min, root->data) && checkbst(root->right,root->data,max) );
  7 
  8 }
  9 
 10 int main()
 11 {
 12         if(checkbst(root, MIN_INT, MAX_INT))
 13                 print "YES";
 14 }

- pseudo_coder. October 11, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Java code: call checkBST (root, Integer.MIN_Value, Integer, MAX_Value)

Boolean checkBST (node root, int min, int max) {
	if(root == null)
		return true;
	if(min < root.data && root.data < max) 
		return checkBST(root.left, min, root.data) && checkBST(root.right, root.data, max);
	else
		return false;
}

- amritaansh123 February 11, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Where you get the max and min value

- Anonymous April 02, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Inorder traversal should give a sorted array if the tree is a BST.

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

I am thinking inorder traversal too.

1. Note the root element.
2. Do inorder traversal of the tree and store in an array.
3. Find the root element in the array.
4. verify if its really sorted.

My question here would be what if the same question was to verify if it was a min or max heap. Then do a preorder traversal?

- Anonymous November 10, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

ur solution though completely valid will still require O(n) space for the array and will have to go through each an every node, although it will still be O(n) time complexity..

how about doing a simple breadth first traversal and before queueing the nodes just checking for the condition:

if (root->left != 0)
{
if (root->data < root->left->data)
{
printf("Not a BST");
break;
}
queue.enqueue(root->left);
}

if (root->right != 0)
{
if (root->data > root->right->data)
{
printf("Not a BST");
break;
}
queue.enqueue(root->right);
}

I think this will work too and will save the extra O(n) space. Also u can abort as soon as u find if its not a BST.

Let me know if something is wrong

- siraj December 03, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I assume you put your code in some while loop. I think you are just comparing left node value and right node value with the root (albeit correctly), but your code doesn't handle all the past parent values in which case you get some errors

like when the tree is

6
/ \
2 8
/ \
1 4
/ \
3 7

This is not a BST but with your code it will say it is, because all it does when the control is at 4 checks if 3 is smaller than 4 and 7 is greater than 4

Let me know if i am missing some thing obvious?

- veeru December 04, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

previous is also correct another possible solution is
find(node*root)
{
if (root!=NULL&&root->left!=NULL&&root->right!=NULL)
if(root->value>root->left->value)&&(root->value<root->right->value)
return true
find(root->left)
find(roo->right)
}

- ramu kumar October 15, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

ramu's solution won't work for a tree like
3
1 6
2 8

- Aries October 22, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

3
/ \
1{ }6
{ }/\
{ }2 8

- Aries October 22, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I guess the recursive code is as follows:

find (node *root)
{
if (root != NULL) // if the node is null return true
{
bool leftNode = find (root->left);
bool rightNode = find (root->right);
if (leftNode && rightNode) //both the criteria should agree else return false
{
if (root->right == NULL && root->left == NULL) //leaf node
return true;
else if (root->right == NULL) //When the right child is null
{
if (root->data > root->left->data)
return true;
else
return false;
}
else if (root->left == NULL) //when left child is null
{
if (root->info < root->right->info)
return true;
else
return false;
}
else
{
if (root->info > root->left->info && root->info < root->right->info)
return true;
else
return false;
}
}
return false;
}
return true;
}

- siraj December 03, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I think this way should be simple and clear, is there anything wrong? Hope to get your critiques.

public static boolean findIsBFS(Node root)
{
if(root==NULL || (!root.leftchild && !root.rightchild))
{
return true;
}
if(root.leftchild.value>root.value || root.rightchild.value<root.value )
{
return false;
}
return findIsBFS(root.leftchild) && findIsBFS(root.rightchild);
}

- wsgis March 05, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

What if only one of the children is present? I think it will be easier if you check each child separately than trying to check both at the same time.

- Sunny December 10, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

<pre lang="" line="1" title="CodeMonkey95493" class="run-this">typedef struct tnode {
int i;
struct tnode* lt;
struct tnode* rt;
} TreeNode;

bool IsValidBST(TreeNode *node, int min, int max)
{
if ((node == NULL) || ((node->lt == NULL) && (node->rt == NULL)))
{
return true;
}
if ((node->i < max) &&
(node->i > min) &&
IsValidBST(node->lt, min , node->i) &&
IsValidBST(node->rt, node->i , max ))
{
return true;
}
}</pre><pre title="CodeMonkey95493" input="yes">The code is very straightforward. as you go down the tree, keep a track of the max and min values that a particular node can take.

you can call this method with MININT and MAXINT values for min and max.

Let me know your comments</pre>

- Anonymous September 17, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

We should leverage properties of binary search tree: the left child value is less or equal to the node value and the right child value should be greater or equal than the node value. And check that property for each node. The code is using preorder traversal.

Assuming that null child is ok.

- melchior October 10, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I agree with the approach. Just want to add that if you do it iteratively, you can also use breadth-first search (with a queue) instead of depth-first search (with a stack).

- Sunny December 10, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Take an in-order traversal of the tree and it should be sorted for a BST

- Brijesh October 10, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Let's assume that all left children are fine, but the root node is not, with large number of children on the left (balanced or non-balanced tree, does not matter), with "in order" traversal the code will have to reach for the last node on the left and only then go up until finding out that the root itself does not comply. It should be fail-fast, fail-early algorithm, which is "pre-order" here. If we were counting non-complied nodes, then the order is irrelevant. Agreed?

- melchior October 10, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

What if the tree is right heavy at the root? And there is a discrepancy wrt to BST near right tree's leaves?

I think inorder traversal will serve fine in general average case.

Also, we can have a mix of both the above approaches.
If node is less than left child or greater than right child, terminate with false.
Else compute inorder. :P

- Learner October 11, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

What you just described as "mix of both" is called "pre-order", exactly the algorithm in the code above.

Pre-order: root -> left child -> right child
In-order: left child -> root -> right child
Post-order: left child -> right child -> root

- melchior October 12, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Can you put example, why if inorder traversal is sorted, then it is not BST ??
I think inorder traversal is sortd ..then definitely it is sorted...

Please exaplain with example

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

1.find the max and min of the given tree, in BST its the right most and left most elements,so thorugh findmax() and findmin() we get the same
2.we increment the minnode and decrement maxnode ,so that the checking we are doing won't fail at the leftmost and rightmost nodes
3.traverse through each node and check wheteher they lie in the suiatable range or not
4.revert back the change we made

typedef struct node
{
int data;
struct node *right;
struct node *left;
}node;
node* findmax(node *root);
node* findmin(node *root);
int check_BST(node *root, int min, int max);

int main()
{
int min,max;
node *root,*maxnode,*minnode;
maxnode= findmax(root);
minnode= findmin(root);
if(maxnode == NULL || minnode ==NULL)
return -1;
min=min->data++;
max-max->node--;
if(check_BST(root,min,max));
printf("\n valid BST");
else
printf("\n non-valid BST");
min->data++;
max->data--;
}

node* findmin(node *root)
{
if(root== NULL)
return NULL;
node *temp1 = malloc(sizeof(node));
if(!temp1)
printf("\n memmory not available");
while(root->left)
root=root->left;
temp1=root;
return temp1;
}
node* findmax(node *root)
{
if(root== NULL)
return NULL;
node *temp2 = malloc(sizeof(node));
if(!temp2)
printf("\n memmory not available");
while(root->right)
root=root->right;
temp2=root;
return temp2;
}

int check_BST( node *root, int min, int max)
{
if(root == NULL)
return 1;
if(root->data < max && root->data >min)
{
return( check_bst(root->left,min,root->data) && check_BST(root->right,root->data, max));
}
else
return 0;
}

- MC October 12, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

1.find the max and min of the given tree, in BST its the right most and left most elements,so thorugh findmax() and findmin() we get the same
2.we increment the minnode and decrement maxnode ,so that the checking we are doing won't fail at the leftmost and rightmost nodes
3.traverse through each node and check wheteher they lie in the suiatable range or not
4.revert back the change we made

typedef struct node
{
int data;
struct node *right;
struct node *left;
}node;
void findmax(node *root,node **maxnode);
void findmin(node *root, node **minnode);
int check_BST(node *root, int min, int max);

int main()
{
int min,max;
node *root,**maxnode,**minnode;
findmax(root);
findmin(root);
if(*maxnode == NULL || *minnode ==NULL)
return -1;
min=(*min)->data++;
max=(*max)->node--;
if(check_BST(root,min,max));
printf("\n valid BST");
else
printf("\n non-valid BST");
(*min)->data++;
(*max)->data--;
}

void findmin(node *root, node **minnode)
{
if(root== NULL)
return NULL;
while(root->left)
root=root->left;
*minnode=root;
}
void findmax(node *root,node **maxnode)
{
if(root== NULL)
return NULL;
while(root->right)
root=root->right;
*maxnode=root;
}

int check_BST( node *root, int min, int max)
{
if(root == NULL)
return 1;
if(root->data < max && root->data >min)
{
return( check_bst(root->left,min,root->data) && check_BST(root->right,root->data, max));
}
else
return 0;
}

- underdog October 12, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

here is simpler code to understand.

bool isThisABST(struct node* mynode)
{
if (mynode==NULL) return(true);

if (node->left!=NULL && mynode->left->info > mynode->data)
return(false);

if (node->right!=NULL && mynode->right->info <= mynode->data)
return(false);

if (!isThisABST(node->left) || !isThisABST(node->right))
return(false);

return(true);
}

- atul October 12, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

correction:-

replace mynode->left->info to mynode->left->data
replace mynode->right->info to mynode->right->data

- atul October 12, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

I think this works. Have to check if the max of the left subtree is less than current node and min of the right subtree is always greater.

struct MinMax {
	int min;
	int max;
};

struct MinMax *IsBST(Node *root)
{
	struct MinMax *newminmax;
	if (!root) return root;
	
	if (!root -> left && !root -> right) {
		newminmax = malloc(sizeof(struct MinMax));
		newminmax -> min = newminmax -> max = root -> value;
		return newminmax;
	}
	
	struct MinMax *left, * right;
	
	left = IsBST(root -> left);
	right = IsBST(root -> right);
	
	if (root -> left) {
		if (!left || left -> max > root -> data)
			return NULL;
		newminmax = left;
	}
	
	if (root -> right) {
		if (!right || right -> min < root -> data)
			return NULL;
		if (!newminmax)
			newminmax = right;
		newminmax -> max = right -> max;
	}
	
	return newminmax;
}

- Ram October 13, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

My recursive solution is as follow :

Bool IsBst ( Tree root )
{
if ( root == NULL )
return true;

if ( ( root->left == NULL && root->right == NULL ) || /* case 1 */
( root->left == NULL && root->data < root->right->data ) || /* case 2 */
( root->right == NULL && root->data > root->left->data ) || /* case 3 */
( root->right != NULL && root->left != NULL && root->data > root->left->data && root->data < root->right->data) ) /* case 4 */
{
return IsBst( root->left ) && IsBst( root->right ) ; /* current node is OK, check children recursively */
}
else
return false ; /* current node is Bad, return false directly */

}

- iatbst January 25, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int arr[10];

void check(tree*root)
{
if(root->left!=NULL)
check(root->left);
arr[i++]=root->val;
if(root->right!=NULL)
check(root->right);


}



int main::
int found=0;

for(int i=0;i<=7; i++)
{


cout<<"\n "<<arr[i];
if((arr[i]>arr[i+1])&&i!=7 )//7 elements
found=1;
}
if (found==0)
cout<<"\nBINARY SEARCH TREE IT IS:SORTED";
else
cout<<"NOT A BINARY SEARCH TREE";
return 0;

- sahil April 22, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int arr[10];

void check(tree*root)
{
if(root->left!=NULL)
check(root->left);
arr[i++]=root->val;
if(root->right!=NULL)
check(root->right);


}



int main::
int found=0;

for(int i=0;i<=7; i++)
{


cout<<"\n "<<arr[i];
if((arr[i]>arr[i+1])&&i!=7 )//7 elements
found=1;
}
if (found==0)
cout<<"\nBINARY SEARCH TREE IT IS:SORTED";
else
cout<<"NOT A BINARY SEARCH TREE";
return 0;

- sahil April 22, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int arr[10];

void check(tree*root)
{
if(root->left!=NULL)
check(root->left);
arr[i++]=root->val;
if(root->right!=NULL)
check(root->right);


}



int main::
int found=0;

for(int i=0;i<=7; i++)
{


cout<<"\n "<<arr[i];
if((arr[i]>arr[i+1])&&i!=7 )//7 elements
found=1;
}
if (found==0)
cout<<"\nBINARY SEARCH TREE IT IS:SORTED";
else
cout<<"NOT A BINARY SEARCH TREE";
return 0;

- sahil April 22, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int arr[10];

void check(tree*root)
{
if(root->left!=NULL)
check(root->left);
arr[i++]=root->val;
if(root->right!=NULL)
check(root->right);


}



int main::
int found=0;

for(int i=0;i<=7; i++)
{


cout<<"\n "<<arr[i];
if((arr[i]>arr[i+1])&&i!=7 )//7 elements
found=1;
}
if (found==0)
cout<<"\nBINARY SEARCH TREE IT IS:SORTED";
else
cout<<"NOT A BINARY SEARCH TREE";
return 0;

- sahil April 22, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int arr[10];

void check(tree*root)
{
if(root->left!=NULL)
check(root->left);
arr[i++]=root->val;
if(root->right!=NULL)
check(root->right);


}



int main::
int found=0;

for(int i=0;i<=7; i++)
{


cout<<"\n "<<arr[i];
if((arr[i]>arr[i+1])&&i!=7 )//7 elements
found=1;
}
if (found==0)
cout<<"\nBINARY SEARCH TREE IT IS:SORTED";
else
cout<<"NOT A BINARY SEARCH TREE";
return 0;

- sahil April 22, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int arr[10];

void check(tree*root)
{
if(root->left!=NULL)
check(root->left);
arr[i++]=root->val;
if(root->right!=NULL)
check(root->right);


}



int main::
int found=0;

for(int i=0;i<=7; i++)
{


cout<<"\n "<<arr[i];
if((arr[i]>arr[i+1])&&i!=7 )//7 elements
found=1;
}
if (found==0)
cout<<"\nBINARY SEARCH TREE IT IS:SORTED";
else
cout<<"NOT A BINARY SEARCH TREE";
return 0;

- sahil April 22, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int arr[10];

void check(tree*root)
{
if(root->left!=NULL)
check(root->left);
arr[i++]=root->val;
if(root->right!=NULL)
check(root->right);


}



int main::
int found=0;

for(int i=0;i<=7; i++)
{


cout<<"\n "<<arr[i];
if((arr[i]>arr[i+1])&&i!=7 )//7 elements
found=1;
}
if (found==0)
cout<<"\nBINARY SEARCH TREE IT IS:SORTED";
else
cout<<"NOT A BINARY SEARCH TREE";
return 0;

- sahil April 22, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int arr[10];

void check(tree*root)
{
if(root->left!=NULL)
check(root->left);
arr[i++]=root->val;
if(root->right!=NULL)
check(root->right);


}



int main::
int found=0;

for(int i=0;i<=7; i++)
{


cout<<"\n "<<arr[i];
if((arr[i]>arr[i+1])&&i!=7 )//7 elements
found=1;
}
if (found==0)
cout<<"\nBINARY SEARCH TREE IT IS:SORTED";
else
cout<<"NOT A BINARY SEARCH TREE";
return 0;

- sahil April 22, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int arr[10];

void check(tree*root)
{
if(root->left!=NULL)
check(root->left);
arr[i++]=root->val;
if(root->right!=NULL)
check(root->right);


}



int main::
int found=0;

for(int i=0;i<=7; i++)
{


cout<<"\n "<<arr[i];
if((arr[i]>arr[i+1])&&i!=7 )//7 elements
found=1;
}
if (found==0)
cout<<"\nBINARY SEARCH TREE IT IS:SORTED";
else
cout<<"NOT A BINARY SEARCH TREE";
return 0;

- sahil April 22, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int arr[10];

void check(tree*root)
{
if(root->left!=NULL)
check(root->left);
arr[i++]=root->val;
if(root->right!=NULL)
check(root->right);


}



int main::
int found=0;

for(int i=0;i<=7; i++)
{


cout<<"\n "<<arr[i];
if((arr[i]>arr[i+1])&&i!=7 )//7 elements
found=1;
}
if (found==0)
cout<<"\nBINARY SEARCH TREE IT IS:SORTED";
else
cout<<"NOT A BINARY SEARCH TREE";
return 0;

- sahil April 22, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int arr[10];

void check(tree*root)
{
if(root->left!=NULL)
check(root->left);
arr[i++]=root->val;
if(root->right!=NULL)
check(root->right);


}



int main::
int found=0;

for(int i=0;i<=7; i++)
{


cout<<"\n "<<arr[i];
if((arr[i]>arr[i+1])&&i!=7 )//7 elements
found=1;
}
if (found==0)
cout<<"\nBINARY SEARCH TREE IT IS:SORTED";
else
cout<<"NOT A BINARY SEARCH TREE";
return 0;

- sahil April 22, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

//7 element

int arr[10];

void check(tree*root) //inorder traverse
{
if(root->left!=NULL)
check(root->left);
arr[i++]=root->val;
if(root->right!=NULL)
check(root->right);


}



int main::

check(root);
int found=0;

for(int i=0;i<=7; i++)
{


cout<<"\n "<<arr[i];
if((arr[i]>arr[i+1])&&i!=7 )//7 elements
found=1;
}
if (found==0)
cout<<"\nBINARY SEARCH TREE IT IS:SORTED";
else
cout<<"NOT A BINARY SEARCH TREE";
return 0;

- sahil munch April 22, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

bool isBinarySearchTree(node *root) {
  return (!root->left ||
          (root->left &&
           root->left->data <= root->data &&
           isBinarySearchTree(root->left)))
    && (!root->right ||
        (root->right &&
         root->right->data > root->data &&
         isBinarySearchTree(root->right)));
}

- J May 02, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Approach

The solution is to check, for every node in the tree, the min and max key values of the nodes in its left sub tree is less than the value of its key and the min and max key values in its right sub tree is greater than the value of its key. This can be achieved by recursion.

The idea is to “bubble up” the min and max values of a node’s sub tree, after satisfying the conditions above, to its parent node, which will in turn repeat the same process. The algorithm is designed around pre-order tree traversal and solves the problem in O(n) (linear) time.

Algorithm

For the current node:

Step1: Get the min and max values for left sub tree if left child exists

Step2: If the min and max values are greater or equal to current node’s key, return “Not BST”

Step 3: If there is no left child, set the min value to current node’s key value

Step 4: Get the min and max values for right sub tree if right child exists

Step 5: If the min and max values are lesser or equal to current node’s key, return “Not BST”

Step 6: If there is no right sub tree, set the min value from step 1 and the max value to current node’s key value

Step 7: Return the min value from step 1 and max value from step 6

You can find the code and the explanation using a pictorial representation of the binary tree in my blog linearspacetime[dot]blogspot[dot]com

- Anonymous May 04, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

bool ifBst(node* p) {
return ((p==null) || (p->data < p->left->data && p->data >= p->right->data && ifBst(p->left) && ifBst(p->right));
}

- Indranil June 05, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Another solution. While traversing inorder keep track of the prev node visited & ensure that every previous node visited has less [or equal] value than the current node value.

- Aashish July 08, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Solution should be Inplace..!!!

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

Please verify this code.....

int check_bst(node *r)
{
   if(r==NULL)
   return 1;
  else
  {
    node *p=r->left;
   node *q=r->right;
   if(p->data<r->data && q->data>r->data)
    { 
        check_bst(p);
       check_bst(q);
     }
   else
      return 0;
  }
}

- prashantsahu13 March 14, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This calls for a recursive solution in which u would at each step check if the left subtree is a BST, right subtree is a BST and the root lies between max of left and min of right subtree.

- srikantaggarwal July 18, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

similar question at: question?id=11146157

- Murali Mohan July 18, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Inorder traversal gives a sorted array if and only if tree is BST!

- Superman July 18, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static boolean isBST(BinaryTree<Integer> binaryTree, Integer lowerBoundExclusive, Integer upperBoundExclusive){
System.out.println("binaryTree: " + binaryTree.getInfo());
BinaryTree<Integer> binaryTreeLeft = binaryTree.getLeftChild();
if(binaryTreeLeft != null && (binaryTree.getInfo().compareTo(binaryTreeLeft.getInfo()) < 1 || (lowerBoundExclusive != null && lowerBoundExclusive.compareTo(binaryTreeLeft.getInfo()) > -1)))
return false;

BinaryTree<Integer> binaryTreeRight = binaryTree.getRightChild();
if(binaryTreeRight != null && (binaryTree.getInfo().compareTo(binaryTreeRight.getInfo()) > -1 || (upperBoundExclusive != null && upperBoundExclusive.compareTo(binaryTreeRight.getInfo()) < 1)))
return false;
boolean isLeftSubTreeBST = binaryTreeLeft == null ? true : isBST(binaryTreeLeft, lowerBoundExclusive, binaryTree.getInfo());
if(!isLeftSubTreeBST)
return false;

boolean isRightSubTreeBST = binaryTreeRight == null ? true : isBST(binaryTreeRight, binaryTree.getInfo(), upperBoundExclusive);
if(!isRightSubTreeBST)
return false;
return true;

}

- Ayan July 19, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

bool isBST(Node* root, int& previousValue)
{
    if ( root )
    {
        if ( !isBST(root->m_left,previousValue) )
        {
            return false;
        }
        std::cout<<"\t"<<root->m_data<<" prev :"<<previousValue;
        if ( root->m_data < previousValue )
        {
            return false;
        }
        previousValue =  root->m_data;
       if ( !isBST(root->m_right, previousValue) )
       {
           return false;
       }
    }
    return true;
}

- Ricky January 29, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This should work, even if MAX_INT or MIN_INT are in the tree -

typedef struct Node {
    struct Node *l, *r;
    int v;
} Node;

// Parse tree from stdin
void parse_tree(Node **);

// Check if tree is BST, and if so get min and max values of tree
int is_bst(Node * node, int *min, int *max)
{
    int lmax, rmin;
    if (node == NULL)
        return 1;
    else
        *max = *min = node->v;

    return  (node->l == NULL ||
                (is_bst(node->l, min, &lmax) && (lmax < node->v))
            ) &&
            (node->r == NULL ||
                (is_bst(node->r, &rmin, max) && (node->v < rmin))
            );
}

int main()
{
    Node *head = NULL;
    parse_tree(&head);
    int max, min;
    is_bst(head, &max, &min) ? printf("BST\n") : printf("BAD\n");
}

- Chaitanya Mangla February 05, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

static int c=Integer.MIN_VALUE;  //global declaration
public static boolean bst(Tree t)
{
   
   if(t.left!=null)
   {
       if(bst(t.left)==false)
       {
           return false;
       }
   }
   if(t.data<c)
   {
       return false;
       
   }
   
   c=t.data;
   if(t.right!=null)
   {
       if(bst(t.right)==false)
           return false;
   }
     return true;      
}

- wolfengineer March 23, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

private static boolean IsBST(BST tree, int rootValue) {

if (tree == null) {
return true;
}
if ((tree.leftNode != null && tree.leftNode.value > rootValue)
&& (tree.rightNode != null && tree.rightNode.value < rootValue)) {
return false;
}
return IsBST(tree.leftNode, rootValue) && IsBST(tree.rightNode, rootValue);
}

- Sunil Tamoli February 01, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

<pre lang="" line="1" title="CodeMonkey73917" class="run-this">/**
* Created by IntelliJ IDEA.
* User: andrey
* Date: 10/10/11
* Time: 10:50 AM
*/
public class BinarySearchTreeOrNot {

public static void main(String[] args) {
BinarySearchTreeOrNot test = new BinarySearchTreeOrNot();
test.run();
}

void run() {

// test with binary search tree
Node bst = createBinarySearchTree();

boolean result = isBinarySearchTreeNode(bst);

System.out.println(result);

// test with binary tree
Node bt = createBinaryTree();

result = isBinarySearchTreeNode(bt);

System.out.println(result);

}

boolean isBinarySearchTreeNode(Node node){

if (node == null) return true;

if (node.left != null && node.left.value > node.value) return false;

if (node.right != null && node.right.value < node.value) return false;

return isBinarySearchTreeNode(node.left) && isBinarySearchTreeNode(node.right);

}

Node createBinarySearchTree(){
Node one = new Node(1);
Node four = new Node(4);
Node three = new Node(3);
three.left = one;
three.right = four;
Node five = new Node(5);
Node six = new Node(6);
Node seven = new Node(7);
Node nine = new Node(9);
five.left = three;
five.right = seven;
seven.left = six;
seven.right = nine;
return five;
}

Node createBinaryTree(){
Node five = new Node(5);
Node eight = new Node(8);
Node one = new Node(1);
Node sixteen = new Node(16);
Node three = new Node(3);
Node nine = new Node(9);
Node two = new Node(2);

five.left = eight;
five.right = three;
eight.left = one;
eight.right = sixteen;
three.left = nine;
three.right = two;

return five;
}


class Node {

int value;

Node right;
Node left;

Node(int value){
this.value = value;
}
}
}
</pre><pre title="CodeMonkey73917" input="yes">
</pre>

- melchior October 10, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

replace
isBinarySearchTreeNode(node.left) && isBinarySearchTreeNode(node.right);

with

isBinarySearchTreeNode(node.left) || isBinarySearchTreeNode(node.right);

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

Care to explain?

|| will check the left part of the condition and if it's true, then return back true, even if the right child is not BST.

&& is correct

- melchior October 12, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

ohh sorry.... didnt read it correctly
its right :) :)

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

Won't work. In the following case. It is a binary tree, but not a valid BST.

10
  /  \
 5   12
  \
   7
  / \
 3   9

- Ram October 13, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Nice test case, Ram!!! You absolutely right! One of the solutions would be to pass the limits, updating them along the way. I rewrote the code and it works for the test case above. I'm glad you posted your comment.

- melchior October 13, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

boolean isBinarySearchTreeNode(Node node, int left, int right){

        if (node == null) return true;

        if (node.value < left || node.value > right) return false;

        if (node.left != null && node.left.value > node.value) return false;

        if (node.right != null && node.right.value < node.value) return false;

        return isBinarySearchTreeNode(node.left, left, node.value) && isBinarySearchTreeNode(node.right, node.value, right);
    }

The same algorithm was posted by pseudo_coder below.

- melchior October 13, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

int arr[10];

void check(tree*root)
{
if(root->left!=NULL)
check(root->left);
arr[i++]=root->val;
if(root->right!=NULL)
check(root->right);


}



int main::
int found=0;

for(int i=0;i<=7; i++)
{


cout<<"\n "<<arr[i];
if((arr[i]>arr[i+1])&&i!=7 )//7 elements
found=1;
}
if (found==0)
cout<<"\nBINARY SEARCH TREE IT IS:SORTED";
else
cout<<"NOT A BINARY SEARCH TREE";
return 0;

- sahil munch April 22, 2012 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

boolean isBST(node root) {
	if ( root == null || (root.left == null && root.right == null )) {
		return true;
	}
	if ( root.left == null && root.right == null ) {
		return true;
	}
	if ( root.left > root.right ) {
		return false;
	}
	return (isBST(root.left) && isBST(root.right));
}

- sjain July 18, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

when you vote down, can you explain about your concern.

- sjain July 18, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@sjain

I haven't voted your comment down, though, after seeing your algorithm I too realized the problem(as probably the other lady/gentleman, who voted down your comment would too have) that the following condition alone is not sufficient.

if ( root.left > root.right ) {
		return false;
	}

You are checking for correctness only at parent-child level, whereas you would need to check for correctness at subtree level.

For ex: Suppose you are at a node in the right subtree of the whole tree and your above condition is satisfied. But, how will you ensure that your

root.left

is greater than all of the elements in the left sub-tree of the whole tree?

The recursive method which takes min and max permissible values as parameters and which checks at each sub-tree level that the node value is lying within those parameters works correctly. You may want to check solutions at: question?id=11146157

- Murali Mohan July 18, 2013 | Flag


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