## Amazon Interview Question for Software Engineer / Developers

Team: Chennei
Country: India
Interview Type: Written Test

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

``````/* check for BST */
private static boolean isBST(BSTNode root) {
if (root == null)
return true;

if (root.getLeft() != null && findMax(root.getLeft()) > root.getData())
return false;
if (root.getRight() != null
&& findMin(root.getRight()) < root.getData())
return false;

if (!(isBST(root.getLeft())) || (!isBST(root.getRight())))
return false;
return true;
}``````

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

``````/* Check for binary tree whether its binary search tree */
private static boolean isBST(BSTNode root, int prev) {
if(root==null)
return true;
if(!isBST(root.getLeft(),prev))
return false;
if(root.getData()<prev)
return false;
prev=root.getData();

return isBST(root.getRight(),prev);
}``````

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

This question can be easily misinterpreted. The conditioin

``left_child < node < right_child``

is not enough to make a binary tree a BST. Given a node n, all descendants to the left must be less than n's value. Likewise, all descendants to the right must be greater than n's value. These bounds must be passed forward in the search.

``````int check_bst(Node *p, int min, int max)
{
if (p == 0)
return 1;

int value = p->value;

if (value > max || value < min)
return 0;

return check_bst(p->left, min, value-1)
&& check_bst(p->right, value+1, max);
}

int is_bst(Node *root)
{
int value = root->value;
return check_bst(root->left, INT_MIN, value-1)
&& check_bst(root->right, value+1, INT_MAX);
}``````

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

``````def isTreeBST(n,min,max):

if(n==None):
return True
if(n.data<min or n.data>max):
return False

if(not(isTreeBST(n.left,min,n.data-1)) or not(isTreeBST(n.right,n.data+1,max))):
return False

return True``````

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

BOOL IsBST(BST *root, int *val)
{
BOOL bRet = TRUE;

if (NULL == root)
{
return TRUE;
}

bRet = IsBST(root->left, val);

if (bRet == TRUE)
{
if (root->data < (*val))
{
bRet = FALSE;
}
else
{
*val = root->data;
}
}

if (TRUE == bRet)
{
bRet = IsBST(root->right, val);
}

return bRet;
}

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

int min = minimum value of integer
int max = maximum value of integer
isBST(Tree node, min, max );

//actual method implementation
isBST(Tree node, int min, int max){

if(node==null)
return true;

if(node.value > min || node.value < max)
return false;

return isBST(node.left,min,node.data-1)&&isBST(node.right,node.data+1,max);

}

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

Do a INORDER trversal. You should get a sorted list.

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

``````/* C# Code */

bool result = IsBST(root, MIN, MAX);

private bool IsBST(TreeNode node, int min, int max)
{
if (node == null)
{
return true;
}

if (node.Value < min || node.Value > max)
{
return false;
}

Debug.WriteLine(string.Format("Current: {0} \t Left: {1} \t Right: {2}", node.Value, node.Left == null ? -1 : node.Left.Value, node.Right == null ? -1 : node.Right.Value));

bool leftBST = false;
bool rightBST = false;

if (node.Left == null || node.Value > node.Left.Value)
{
leftBST = true;
}

if (node.Right == null || node.Value < node.Right.Value)
{
rightBST = true;
}

if (leftBST && rightBST)
{
return IsBST(node.Left, min, node.Value) && IsBST(node.Right, node.Value, max);
}
else
{
return false;
}
}``````

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

``````static class Node {
public Node left;
public Node right;
public int data;
}
public boolean isBst(Node node)
{
return isBinarySearchTree(node , Integer.MIN_VALUE , Integer.MAX_VALUE);
}
public boolean isBinarySearchTree(Node node , int min , int max)
{
if(node.data < min || node.data > max)
return false;
//Check this node!
//This algorithm doesn't recurse with null Arguments.
//When a null is found the method returns true;
//Look and you will find out.
/*
* Checking for Left SubTree
*/
boolean leftIsBst = false;
//If the Left Node Exists
if(node.left != null)
{
//and the Left Data are Smaller than the Node Data
if(node.left.data < node.data)
{
//Check if the subtree is Valid as well
leftIsBst = isBinarySearchTree(node.left , min , node.data);
}else
{
//Else if the Left data are Bigger return false;
leftIsBst = false;
}
}else //if the Left Node Doesn't Exist return true;
{
leftIsBst = true;
}

/*
* Checking for Right SubTree - Similar Logic
*/
boolean rightIsBst = false;
//If the Right Node Exists
if(node.right != null)
{
//and the Right Data are Bigger (or Equal) than the Node Data
if(node.right.data >= node.data)
{
//Check if the subtree is Valid as well
rightIsBst = isBinarySearchTree(node.right , node.data+1 , max);
}else
{
//Else if the Right data are Smaller return false;
rightIsBst = false;
}
}else //if the Right Node Doesn't Exist return true;
{
rightIsBst = true;
}

//if both are true then this means that subtrees are BST too
return (leftIsBst && rightIsBst);
}``````

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.