## Microsoft Interview Question for Software Engineer / Developers

Country: India
Interview Type: In-Person

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

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

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

right answer. this guys is lucky

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

checking for sorted array after whole tree traversal would just add to time complexity.
It could be checked during traversal only.

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

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
}

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

Here is my implementation:

basicalgos.blogspot.com/2012/03/25-binary-search-tree-verification.html

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

The above implementation requires O(N) space complexity. Can we solve it with less space?

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

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

}

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

Wrong a bit.

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

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

Wrong a bit.

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

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

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

}

Comment hidden because of low score. Click to expand.
0
this may give wrong result consider following tree {{{3}}} {{2}} {{{{{{6}}}}}} {1} {{{4}}} {{{{{{5}}}}} {{{{{{{{8}}}}}}}} This is not a bst bt ur algo will return yes
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

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

Simplest way to do is :-
At any node check if max_of_left_sub_tree is greater than current node value and check if min_of_right_sub_tree is smaller than current node value. If this condition meets, return false otherwise make a function call left and right nodes.

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

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 .

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

seems the best solution . no extra space required .. with time completixy O(N)

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.