## Amazon Microsoft Interview Question for Software Engineer / Developers

• 0

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

see prev threads ..solution using INT_MAX AND INT_MIN

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

make a inorder traversal of a given tree and if the traversal is in sorted form then the given tree is BST.
10
/ \
5 15
/\ /\
3 8 13 18

Inorder: 3,5,8,10,13,15,18

output will always be sorted for inorder traversal of BST

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

bool checkBST(tree * root, int min, int max)
{
if (root->data < min || root->data > max)
{
return false;
}
bool left = true, right = true;
if (root->left != NULL)
{
left = checkBST(root->left, min, root->data)
}
if (root->right != NULL)
{
right = checkBST(root->left, root->data, max)
}
return left & right;
}

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

does count the nodes

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

``````struct node {
node *left;
node * right;
int data;
};
bool inorder(node * root) {
static bool isBST = 1;
static int count = 0;
if(root) {
inorder(root->left);
chk_BST(root,isBST);
count++;
inorder(root->right);
}
else{
cout<<"No. of nodes = "<<count;
return isBST;
}
}

chk_BST(node * root,bool isBST) {
if(root->left) {
if(root->data<root->left->data) {
isBST = 0;
}
}
if(root->right) {
if(root->data>root->right->data) {
isBST = 0;
}
}
}``````

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

Seems like this would print count whenever the node is null, which is the children of all the leaves.

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

Perform an inorder traversal of the tree and print all the node data. If the node data is in ascending order then it is a binary search tree. To count the number of nodes, keep a counter while traversing the tree inorder.

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

Detailed description for the above problem with two possible solutions is described here

crackinterviewtoday.wordpress.com/2010/03/12/check-whether-given-binary-tree-is-a-bst-or-not/

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

Using INT_MAX and INT_MIN only applicable if BST hold ints as data. If BST has elements that do not have natural ordering or, if they do, do not have min and max values (eg. strings), in-order traversal may work better (assuming BST elements have ordering/are comparable) save for the extra space requirement

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

``````template<typename T>
class TreeNode
{
public:
TreeNode() {};
~TreeNode() {};

TreeNode* left;
TreeNode* right;

T data;
};

template<typename T>
bool isBST(TreeNode<T>* root)
{
static int count = 0;
static bool bIsBST = true;
static TreeNode<T>* pLastVisited = NULL;

if (root)
{
isBST(root->left);

cout++;
if (pLastVisited && pLastVisited->data > root->data)
bIsBST = false;
pLastVisited = root;

isBST(root->right);
}

return bIsBST;
}``````

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

``````bool isBST(node * root) {
bool isbst = true;
isbst &= root->left ? isBST(root->left) & (root->left->value < root->value):true;
isbst &= root->right ? isBST(root->right) & (root->right->value > root->value):true;
return isbst;
}``````

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

Your does not work for the following binary tree.

1
/
5
\
6

This is not a BST. But your code returns true.

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

int TreeCount = 0;
bool IsBST(TreeNode root)
{
return (NULL == root) ? true:
(TreeCount++ , (!root->left || (root->left->info <= root->info)) &&
(!root->right || (root->right->info <= root->info)) &&
IsBST(root->left) &&
IsBST(root->right));
}

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

int inorder(struct node *cur, struct node *prev)
{
int flag1, flag2;
if(cur==NULL) return 1;
flag1 = inorder(cur->left, prev);
if(prev==NULL) prev = cur;
else if(prev->data>cur->data) return 0;
flag2 = inorder(cur->right, cur);
return flag1 && flag2;
}

if(inorder(root, NULL)) print BST
else print not BST

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

Correction - Question is to find if a given binary tree is a binary search tree or not.

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

bool IsBinarySearchTree(Tree root)
{
if (root == null) return true;
if ((root.left != null && root.left.value > root.value) ||
(root.right != null && root.right.value < root.value))
return false;
return IsBinarySearchTree(root.left) && IsBinarySearchTree(root.right);
}

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

this will fail for this tree

``````5
3        7
1   8    6    9``````

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

How is that a binary search tree at all ....

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

the given tree has 8 in incorrect place.

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

That is the point zoom.anshu is trying to make. The above tree is not a binary tree; but you algo will report true.

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

public bool IsItBinarySearchTree(Node node, int data)
{
bool status = true;
if (node != null)
{
if (data > node.data)
{
status = false;
}

if (node.left != null)
{
status = (node.left.data > node.data) ? false : true;
if (status)
{
status = IsItBinarySearchTree(node.left, node.left.data);
}
}

if (status && node.right != null)
{
status = IsItBinarySearchTree(node.right, node.data);
}
}

return status;
}

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

For invoking the above function, pass root & root.data

i.e. IsItBinarySearchTree(root, root.data);

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

Do inorder traversal. It should be sorted.

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

This is necessary but not sufficient condition.

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

I think this will work - what you think is missing when you say it not sufficient?

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

3
/
5

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

``````static int max_so_far = -infinity;
public isBST(Node root) {
if (root==null) return true;
boolean leftBST = isBST(root.left);
if (root.value>max_so_far) {
max_so_far = root.value;
}
else {
return false;
}
return leftBST && isBST(root.right);
}``````

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

isbinarysearch(node*root)
{
if(root==NULL)
return;
if(root->left)
{ if(root->left->data>root->data)
return false
}
if(root->right)
{
if(root->right->data<root->data)
return false
}
return true

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

sorry for this it will not work

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

isbinarysearch(node*root)
{
if(root==NULL)
return;
if(root->left)
{ if(root->left->data>root->data)
return false
}
if(root->right)
{
if(root->right->data<root->data)
return false
}
return true
isbinarysearch(root->left)
isbinarysearch(root->right)

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

``````bool isBST(Node *tree,int *nodeCount)
{
if(tree)
{
bool result=true;

if(tree->left==NULL && tree->right==NULL)
{
(*nodeCount)++;
return true;
}
else
{
if(tree->left)
{
result=result && isBST(tree->left,nodeCount);
}

if(tree->right)
{
result=result && isBST(tree->right,nodeCount);
}

result=result && (tree->left && tree->left->value < tree->value) && (tree->right && tree->right->value >= tree->value);

*nodeCount++;
return result;
}
}
else
return false;
}``````

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

Just Inorder traverse the tree and determine the preNode < currentNode is fine
PNode IsBSTCore(PTree tree, PNode &pPreNode)
{
if(tree)
{
PNode pNode = IsBSTCore(tree->left, pPreNode);
if(pNode) return pNode;
if(pPreNode && pPreNode->data > tree->data)
{
return tree;
}
printf("%d\t%d\t", pPreNode? pPreNode->data : -1, tree->data);
pPreNode = tree;
pNode = IsBSTCore(tree->right, pPreNode);
return pNode;
}
return tree;
}
PNode IsBST(PTree tree)
{
assert(tree != NULL);
PNode pNode = NULL;
return IsBSTCore(tree, pNode);
}

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

this will return that binary tree is bst or not and also the no of nodes in the binary tree

int checkBST(struct node *r,int *count)
{
if(r==NULL)
return 1;
count++;
if(r->left && r->left->data>r->data)
k=0;
if(r->right && r->right->data<r->data)
k=0;
return(k && checkBST(r->left)&&chackBST(r->right));
}

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.