## Amazon Interview Question for SDE-2s

Country: United States
Interview Type: In-Person

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

the question asks for a Valid Binary Tree, not a valid Binary Search Tree, so, the min max should not be a concern, rather whether the tree has two children per node at most.

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

The question is "checking the tree is Binary Tree"
However the code is Binary Search Tree...
So I think the question might be typing error????

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

Binary tree will have atmost 2^h-1 nodes (full binary tree). Count the number of nodes and see if n <= 2h^-1 (n=number of nodes, h=height of the tree). If its satisfies this condition then the tree is said to be binary tree.

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

public boolean isBinaryTree(Node root) {
if (root == null) return true;
else if (root.children.length > 2) return false;
return isBinaryTree(root.children[0]) && isBinaryTree(root.children[1]);
}

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

``````public class BST {

private static Node prevNode = null;

public boolean isBST(Node root){
if (root != null){
if (!isBST(root.left)){
return false;
}
if (prevNode != null && prevNode.data >= root.data){
return false;
}
prevNode = root;
return isBST(root.right);
}
return true;
}``````

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

fdsafdsa

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

static boolean checkBST(Node root, int minValue, int maxValue)
{
if(root == null)
return true;
else if( root.data > minValue && root.data < maxValue && checkBST(root.left,minValue,root.data)
&& checkBST(root.right,root.data,maxValue))
return true;
else
return false;
}

static boolean checkBST(Node root) {
if(root == null)
return true;
/* 2nd approach : O(n2)
* else if(isLeftSubtreeLesser(root.left,root.data) && isRightSubtreeGreater(root.right,root.data) && checkBST(root.left) && checkBST(root.right))
return true;*/
// 1st Approach : O(n)
else if(checkBST(root,Integer.MIN_VALUE, Integer.MAX_VALUE))
return true;
else
return false;
}

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

you could iterate the tree in an in-order fashion, you need to check if your values are ordered :)

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

/**
* Binary Search Tree ,value of left child must be less than value of parent, value of right child must be greater
* than value of parent
* Then we can use inorder traversal, if BST , after in order, all value of node must be sorted
* if previous value is greater current value is invalid
*/
public boolean isValidBSTCaller(TreeNode root) {
int prev = Integer.MIN_VALUE;
return isValidBST(root, prev);
}

public boolean isValidBST(TreeNode root, int prev) {
if (root==null) return true;
return (isValidBST(root.left,prev)) && (root.data>= prev) && isValidBST(root.right,prev=root.data);
}

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

public boolean isValidBSTCaller(TreeNode root) {
int prev = Integer.MIN_VALUE;
return isValidBST(root, prev);
}
// BST, left key <= parent key, right key >= parent key, inorder list sorted key data
// once prev key > current key, invalid
public boolean isValidBST(TreeNode root, int prev) {
if (root==null) return true;
return (isValidBST(root.left,prev)) && (root.data>= prev) && isValidBST(root.right,prev=root.data);
}

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

``````struct node* check(struct node* root)
{
struct node* true=NULL;
struct node* false;
int key=root->data;
if(root==NULL)
return true;
if(key > root->right->data || key <= root->left->data)
return false;
if(key<root->right)
return check(root->right);
if(key>root->left)
return check(root->feft);
}

boolean getBinary()
{
struct node* a;
if(a)
return true;
else
return false;
}``````

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

``````struct node* check(struct node* root)
{
struct node* true=NULL;
struct node* false;
int key=root->data;
if(root==NULL)
return true;
if(key > root->right->data || key <= root->left->data)
return false;
if(key<root->right)
return check(root->right);
if(key>root->left)
return check(root->feft);
}

boolean getBinary()
{
struct node* a;
if(a)
return true;
else
return false;
}``````

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

``````static boolean checkBST(Node root, int minValue, int maxValue)
{
if(root == null)
return true;
else if( root.data > minValue && root.data < maxValue && checkBST(root.left,minValue,root.data)
&& checkBST(root.right,root.data,maxValue))
return true;
else
return false;
}

static boolean checkBST(Node root) {
if(root == null)
return true;
/* 2nd approach : O(n2)
* else if(isLeftSubtreeLesser(root.left,root.data) && isRightSubtreeGreater(root.right,root.data) && checkBST(root.left) && checkBST(root.right))
return true;*/
// 1st Approach : O(n)
else if(checkBST(root,Integer.MIN_VALUE, Integer.MAX_VALUE))
return true;
else
return false;
}``````

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

Using min-max approach:

``````public static boolean isValidBST(TreeNode root) {
if (root == null) {
return true;
}
return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
}

// int min, int max version
public static boolean isValidBST(TreeNode root, long min, long max) {
if (root == null) {
return true;
}
if (root.val <= min || root.val >= max) {
return false;
}
return isValidBST(root.left, min, root.val) &&
isValidBST(root.right, root.val, max);
}``````

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

``````struct node* check(struct node* root)
{
struct node* true=NULL;
struct node* false;
int key=root->data;
if(root==NULL)
return true;
if(key > root->right->data || key <= root->left->data)
return false;
if(key<root->right)
return check(root->right);
if(key>root->left)
return check(root->feft);
}

boolean getBinary()
{
struct node* a;
if(a)
return true;
else
return false;
}``````

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.