## Amazon Interview Question for Software Engineer in Tests

Country: United States
Interview Type: Phone Interview

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

``````/*
balanced: check if a binary tree is balanced.
*/

#include <assert.h>
#include <stdlib.h>
#include <stdio.h>

/* standard tree node */
struct treenode {
struct treenode *left;
struct treenode *right;
};

/* max of two integers */
int
max(int a, int b)
{
return (a > b) ? a : b;
}

/* start by assuming tree rooted at node is balanced.  Recurse
to find left and right subtree heights.  Set balanced to false
if tree rooted at node is not balanced.  Leaf height is 0
and leaf is balanced.

Note that balanced is untouched or set to false.
*/
int
height(struct treenode *node, int *balanced)
{
if (!node)
return 0;
int leftheight = height(node->left, balanced);
int rightheight = height(node->right, balanced);
if (abs(leftheight - rightheight) > 1)
*balanced = 0;
return max(leftheight, rightheight) + 1;
}

int
main(void)
{
struct treenode rightrightleaf = {
.left = NULL,
.right = NULL
};
struct treenode right = {
.left = NULL,
.right = &rightrightleaf
};
struct treenode root = {
.left = NULL,
.right = &right
};
int balanced = 1;
height(&root, &balanced);
printf("Tree is %s\n", balanced ? "balanced" : "not balanced");
return 0;
}``````

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

In these two sentences "int leftheight = height(node->left, balanced); int rightheight = height(node->right, balanced);" If the left subtree is not balanced, while the right one is balanced, will the variable "balanced" change to 1 again?

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

private static int height(BSTNode n)
{
if (n==null)
return 0;
else return max(height(n.lChild),height(n.rChild))+1;
}
private static int max(int a , int b)
{
return (a>=b?a:b);
}
public boolean balanced()
{
int diff = Math.abs(height(root.left)-height(root.right));
if (diff >1)
return false;
else return true;
}

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

only need to check max_depth-min_depth<=1

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

Just curious and pardon my ignorance. I have seen "WAP" in other questions. Why is it called WAP?

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

WAP means "Write a Program".. :)

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

github.com/techpanja/interviewproblems/blob/master/src/trees/treeproblems/CheckBalancedTree.java

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

Balanced Tree: for each node, the difference between left subtree and right subtree should be less than or equal to 1 and left and right subtree should be balanced.

int height(Node root) {
if(root==null)
return 0;
else
return (max(height(root.left),height(root.right)) +1);
}

boolean balanced(Node root) {

int diff = Math.abs(height(root.left) - height(root.right));
if(root == null)
return true;
else {
if (root.left ==null && root.right == null)
return true;
else if (diff <=1 && balanced(root.left) && balanced(root.right))
return true;
else
return false;
}
}

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

``````Balanced Tree: for each node, the difference between left subtree and right subtree should be less than or equal to 1 and left and right subtree should be balanced.

int height(Node root) {
if(root==null)
return 0;
else
return (max(height(root.left),height(root.right)) +1);
}

boolean balanced(Node root) {

int diff = Math.abs(height(root.left) - height(root.right));
if(root == null)
return true;
else {
if (root.left ==null && root.right == null)
return true;
else if (diff <=1 && balanced(root.left) && balanced(root.right))
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.