## Amazon Interview Question for Senior Software Development Engineers

Country: India
Interview Type: In-Person

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

A binary tree is a BST if and only if:

1. The left sub tree is a BST.
2. The right sub tree is a BST.
3. The left sub tree is null, or the maximum value of the left sub tree is smaller or equal to the node value.
4. The right sub tree is null, or the minimum value of the right sub tree is larger or equal to the node value.

``````bool is_bst(node_t* n, int& min_val, int& max_val)
{
if (nullptr == n) return true;
int min_sub = std::numeric_limits<int>::max();
int max_sub = -std::numeric_limits<int>::max();
if  (!is_bst(n->left, min_sub, max_sub) || max_sub > n->value) return false;
min_val = min_sub;
if (!is_bst(n->right, min_sub, max_sub) || min_sub < n->value) return false;
max_val = max_sub;
min_val = std::min(min_val, n->value); // in case n->left is nullptr
max_val = std::max(max_val, n->value); // in case n->right is nullptr
return true;
}``````

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

say the BST cannot have two particular value like -1 and 0
Then following method solves it. It's a binary search tree if the method does not return -1

``````public int preOrd(Node root){
if(root==null){
return 0;
}
int val = root.getValue();
int lVal=preOrd(root.getLChild);
int rVal=preOrd(root.getRChild);
if(lVal==-1){
return -1;
}
if(rVal==-1){
return -1;
}
if(lVal!=0&&lVal>val){
return -1;
}
if(rVal!=0&&rVal<val){
return -1;
}
return val;
}``````

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

Following method solves this. If it returns null, that means it is not a BST.

``````public ArrayList<Integer> inOrder(Node root){
if(root==null){
return new ArrayList<Integer>();
}
ArrayList<Integer> leftNodes = inOrder(root.getLChild());
if(leftNodes!=null){
int size=leftNodes.size();
if(size>0){
Node last = leftNodes.get(size-1);
if(last.getValue()>root.getValue()){
return null;
}

}
}else{
return null;
}
ArrayList<Integer> rightNodes = inOrder(root.getRChild());
if(rightNodes!=null){
int size=rightNodes.size();
if(size>0){
Node first = rightNodes.get(0);
if(first.getValue()<root.getValue()){
return null;
}

}
}else{
return null;
}
return leftNodes;
}``````

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

I would propose the following: If the binary tree is BST, at any given node as a root, it has the following properties:
(i) The left most node in the right subtree is greater or equal to the root.
(ii) The right most node in the left subtree is less than a root.

Given the root of a binary tree one can recursively check for these two properties. A sample code is shown below:

``````public static boolean isBST(Node root) {
return checkLeft(root, root.val) && checkRight(root, root.val);
}

private static boolean checkRight(Node x, int val) {
if (x == null) 	return true;
if (x < val)	return false;
return checkRight(x.right, val);
}

private static boolean checkLeft(Node x, int val) {
if (x == null) 	return true;
if (x >= val)	return false;
return checkLeft(x.right, val);
}``````

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

``````public boolean isBST(Node n) {

if (n == null) {

return true;
}

Node left, right;
left = n.left;
right = n.right

boolean leftCondition, rightCondition;

leftCondition = (left == null) ? true : (left.value < n.value) ? true : false;
rightCondition = (right == null) ? true : (right.value > n.value) ? true : false;

return leftCondition && rightCondition && isBST(n.left) && isBST(n.right);

}``````

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

Following method solves this. If it returns null, that means it is not a BST.

``````public ArrayList<Integer> inOrder(Node root){
if(root==null){
return new ArrayList<Integer>();
}
ArrayList<Integer> leftNodes = inOrder(root.getLChild());
if(leftNodes!=null){
int size=leftNodes.size();
if(size>0){
Node last = leftNodes.get(size-1);
if(last.getValue()>root.getValue()){
return null;
}

}
}else{
return null;
}
ArrayList<Integer> rightNodes = inOrder(root.getRChild());
if(rightNodes!=null){
int size=rightNodes.size();
if(size>0){
Node first = rightNodes.get(0);
if(first.getValue()<root.getValue()){
return null;
}

}
}else{
return null;
}
return leftNodes;
}``````

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

At any given node, pass along the valid range of the node's value.
When you recurse left and right, constrain the range.

Ex. something like this (note that the edge cases aren't quite correct here as they assume distinct values, but this is easy to change and depends on your definition of the BST)

``````boolean isBST(Node n) {
return isBST(n, Integer.MIN, Integer.MAX);
}
boolean isBST(Node n, int left, int right) {
if (n.val < left || n.val > right) {
return false;
}
return isBST(n.left, left, n.val - 1) && isBST(n.right, n.val + 1, right);
}``````

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

Go on parsing till you get a condition which tells you that the tree isn't sorted

``````private boolean isTreeBST(Node root) {
if (root == null) return true;

if (root.getLeft() != null &&
root.getValue() < root.getLeft().getValue()) {
return false;
}

if (root.getRight() != null &&
root.getValue() > root.getRight().getValue()) {
return false;
}

if(!isTreeBST(root.getLeft()) ||
!isTreeBST(root.getRight())) {
return false;
}

return true;
}``````

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

``````package in.blogspot.randomcompiler;

class TreeNode {
int data;
TreeNode left;
TreeNode right;
}

public class CheckBST {

public static void main(String[] args) {
TreeNode n1 = new TreeNode();
n1.data = 100;

TreeNode n2 = new TreeNode();
n2.data = 75;
n1.left = n2;

TreeNode n3 = new TreeNode();
n3.data = 125;
n1.right = n3;

TreeNode n4 = new TreeNode();
n4.data = 50;
n2.left = n4;

TreeNode n5 = new TreeNode();
n5.data = 90;
n2.right = n5;

System.out.println(isBST(n1));
}

private static boolean isBST(TreeNode root) {
if(root == null) return true;
boolean isBSTLeft = isBST(root.left);
boolean isBSTRight = isBST(root.right);
boolean gtLeft = root.left == null? true : root.data >= root.left.data;
boolean ltRight = root.right == null? true : root.data < root.right.data;
return isBSTLeft && isBSTRight && gtLeft && ltRight;
}

}``````

Output:
true

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

``````bool CheckBST(node *root)
{
Bool left,right;

if (root==NULL)
return (1);

if (root->right !=NULL && getLeft(root-right) < root->value)
return 0;
if (root->left !=NULL && getRight(root->left) > root->value)
return 0;

left=CheckBST(root->left);
right=CheckBST(root->right);

return (left && right);
}

int getLeft(node *root)
{
int val = root->value;
while (root->left!=NULL)
{
root= root->left;
val = root->value;
}
return val;
}

int getRight(node *root)
{
int val = root->value;
while (root->right!=NULL)
{
root= root->right;
val = root->value;
}
return val;
}``````

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

{

isBST(Node root){

RetVal lRet = isBST(root.left());
if(!lRet.isBST())
return new RetVal(false,null,null);

RetVal rRet = isBST(root.right());
if(!rRet.isBST())
return new RetVal(false,null,null);

if((lRet.max()==null || lRet.max().value() <= root.value())
&&(rRet.min()==null || rRet.min().value() >= root.value()))

return new RetVal(true, lRet.min()!=null?lRet.min():root ,rRet.max()!=null? rRet.max():root);

return new RetVal(false,null,null);

}

}

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

public static boolean isBST(TreeNode root){
if(root == null) return true;
if(root.leftChild != null && root.leftChild.data > root.data) return false;
if(root.rightChild != null && root.rightChild.data < root.data) return false;

return isBST(root.leftChild) && isBST(root.rightChild);

}

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

You can use recursive approach to solve this problem. Here is a pseudo code

``````IsBST(Tree t, int min, int max)
{
// if (t == null) {
return true;
}
if (t.data < min || t.data > max)
{
return false;
}
IsBST(t.right, min, t.data) && IsBST(t.left, t.data, max);
}``````

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

``````public class IsBST {

public static boolean isBST(TreeNode node) {
if(node.left == null & node.right == null) {
return true;
} else if(node.left == null ) {
isBST(node.right);
} else if(node.right == null ) {
isBST(node.left);
} else {
return Integer.parseInt(node.left.data) < Integer.parseInt(node.data) &&   Integer.parseInt(node.right.data) >  Integer.parseInt(node.data) ?
isBST(node.right) && isBST(node.left) :false;
}
return false;
}

}``````

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

this is wrong algorithm

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.