## Microsoft Interview Question

Software Engineer / Developers**Country:**India

**Interview Type:**In-Person

This is the correct solution. Found it in geeksforgeeks.org.

int isBST(struct node* node)

{

return(isBSTUtil(node, INT_MIN, INT_MAX));

}

/* Returns true if the given tree is a BST and its

values are >= min and <= max. */

int isBSTUtil(struct node* node, int min, int max)

{

/* an empty tree is BST */

if (node==NULL)

return 1;

/* false if this node violates the min/max constraint */

if (node->data < min || node->data > max)

return 0;

/* otherwise check the subtrees recursively,

tightening the min or max constraint */

return

isBSTUtil(node->left, min, node->data-1) && // Allow only distinct values

isBSTUtil(node->right, node->data+1, max); // Allow only distinct values

}

bool inorder(node *root)

{

if(!root)

return true;

static node *prev=NULL;

Inorder(root->left);

//if it is not sorted

if(prev!=NULL && root->data < prev->data)

return false;

prev=root;

Inorder(root->right);

}

Wrong a bit.

```
...
if (!Inorder(root->left)) return false;
...
return Inorder(root->right);
```

int Is_BST ( node* root ) {

if ( root == NULL ) return 1;

if ( root.Key > root.Right.Key ) return 0;

if ( root.Key < root.Left.Key ) return 0;

return ( Is_BST(root.Right) && Is_BST(root.Left));

}

I give two solutions with same time and space complexity:

The first solution uses the feature of numbers being sorted in in-order traversing. The signature is like "bool IsBST(Node root, ref int lastValue)" in C#.

1. if root is null then return true;

2. if IsBST(root.lchild, ref lastValue) is false then return false. (It means that the left sub-tree of root is not BST)

3. if lastValue >= root.value then return false. (It means that the root is smaller than the biggest value in its left sub-tree)

4. lastValue=root.value

5. return IsBST(root.rchild, ref lastValue)

This solution is used like :

int lastValue=int.MinValue;

IsBST(root, lastValue);

The second solution uses the boundary feature of BST. The signature of method is like "bool IsBST(Node root, int min, int max)" in C#

1. if root is null then return true.

2. return (root.value>min&&root.value<max)&&IsBST(root.lchild, min, root.value)&&IsBST(root.rchild,root.value,max)

This solution is used like:

IsBST(root, int.MinValue, int.MaxValue);

Do Inorder traversal ( either using recursion or iterative version ) ..

the element that you first print store it in prev .

from next time onwards , the element that you are supposed to print in inorder traversal , you make sure that as curr , and compare curr with prev , to make sure that curr > prev .

now replace your prev with curr .

at any point of time if curr < prev then it is not a BST , otherwise it is .

Do inorder traversal.if outcome is sorted than it is a bst.

- Anonymous March 13, 2012