## Amazon Interview Question for SDE-3s

Team: Amazon Fresh
Country: United States
Interview Type: Phone Interview

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

This is easy one, Same as height balance.

Rather than increment by 1, you have to increment by the node->data

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

Assum root of the tree is given, you can do recursive in-order call to right and left subtrees and get the sum.

``````sumTree(struct tree* node, int *sum) {
if(node == NULL) {
return;
}
/* Do in order traversal */
sumTree(node->left, sum);
*sum = *sum + node->data;
sumTree(node->right, sum);
}

int main() {
int rightSum = 0;
int leftSum = 0;
sumTree(root->left, &leftSum);

sumTree(root->right, &rightSum);

if(leftSum == rightSum) {
printf("Tree  is balanced \n");
}else {
printf("Tree not balanced \n");
}
}``````

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

I think the allBalancedNodes() can be achieved in O(n) with post Order traversal.

Have a variable called total in the node like below:

``````class Node
{
int total;  // -- a variable indicating sum seen until now

int key;
int value;

Node left;
Node right;
Node parent;
}``````

isBalanced() definition:

``````public boolean isBalanced()
{
return ( ( left == null && right == null ) || ( left != null && right != null && left.total == right.total ) );
}``````

Post order traversal updating total on each node :

``````public void postOrderTraversal( Node node )
{
if ( node == null ) return;
postOrderTraversal( node.left );
postOrderTraversal( node.right );

node.total = node.value;
if ( node.left != null ) node.total += node.left.total;
if ( node.right != null ) node.total += node.right.total;

System.out.println( " Is balanced : " + node.isBalanced() );
}``````

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

In the example above, shouldn't it be

``[12].isBalanced() -> False.  [3, 5]``

?

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

``````import java.util.List;
import java.util.Queue;
import java.util.ArrayList;

public class BalanceSumBinaryTree
{
public static void main(String[] args)
{
TreeNode root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(1);

root.right.left = new TreeNode(1);

BalanceSumBinaryTree b = new BalanceSumBinaryTree();
System.out.println(b.isBalance(root));
System.out.println(b.allBalanceNodes(root));
}

public boolean isBalance(TreeNode root)
{
if(root==null)
return true;

int left = helper(root.left);
int right = helper(root.right);

return left==right;
}

private int helper(TreeNode root)
{
if(root==null)
return 0;
int left = helper(root.left);
int right = helper(root.right);

return left + root.val + right;
}

public List<TreeNode> allBalanceNodes(TreeNode root)
{
Queue<TreeNode> curr;
next.offer(root);

List<TreeNode> res = new ArrayList<>();

while(!next.isEmpty())
{
curr = next;

while(!curr.isEmpty())
{
TreeNode temp = curr.poll();
if(isBalance(temp))

if(temp.left!=null)
next.offer(temp.left);
if(temp.right!=null)
next.offer(temp.right);
}
}
return res;
}
}

class TreeNode
{
int val;
TreeNode left;
TreeNode right;

TreeNode(int val)
{
this.val = val;
}

public String toString()
{
return this.val+" ";
}
}``````

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.