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

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

that's my solution... :)

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

int arr;
//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;

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

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

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

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

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

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

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

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

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

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

Where you get the max and min value

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.

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

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?

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

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

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

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?

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

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

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

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

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

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

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

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.

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.

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.

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

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

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

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

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?

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

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

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

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

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

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

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

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

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

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

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

correction:-

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

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

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 */

}

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

int arr;

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;

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

int arr;

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;

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

int arr;

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;

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

int arr;

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;

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

int arr;

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;

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

int arr;

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;

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

int arr;

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;

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

int arr;

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;

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

int arr;

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;

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

int arr;

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;

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

int arr;

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;

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

//7 element

int arr;

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;

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

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

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

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.

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

Solution should be Inplace..!!!

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

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

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.

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

similar question at: question?id=11146157

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!

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;

}

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

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()
{
int max, min;
}``````

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

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

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>

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

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

with

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

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

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

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

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

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

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

``````10
/  \
5   12
\
7
/ \
3   9``````

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

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.

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

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

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

int arr;

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;

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

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

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

@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

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.