## Amazon Interview Question

Country: India

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

``````if( head == NULL )
return true;

int rightValue = 0, leftValue = 0;

if( leftValue + rightValue != headValue)
return false;
else

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

``````bool isSumTree(node* head)
{
return true;

int rightValue = 0, leftValue = 0;

if( leftValue + rightValue != headValue)
return false;
else
}``````

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

why not take
static int rightValue, leftValue;
rightValue = 0;
leftValue = 0;

It will save stack while recursion.

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

Thats a good observation ... thanks

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

The case when both the left and right nodes are NULL is not handled. The code should return TRUE, when both the left and right nodes are NULL. Else for all the Leaf nodes with value greater than 0, the function will return FALSE.

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

bool isSumTree(Node root){

if(root==null) return true;

if(!root->left&&!root->right) return true;

if(root.data==root->left.data+root->right.data)
return true;

if(!root->left&&root->right)
return isSumTree(root->right);

if(!root->right&&root->left)
return isSumTree(root->left);

else if(root->left&&root->right)
return (isSumTree(root->left)&&isSumTree(root->right));

}

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

Your code will end when the root sum is equal to the sum of adjacent children. it will not go further..

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

Assuming the property must hold at all nodes and not just the root

``````public class SumTree {
private static class Node {
int key;
Node left;
Node right;
}

Node root;

private boolean isSumTree(Node node) {
if (node == null) {
return true;
}
if (node.left == null && node.right == null) {
return true;
}
if (isSumTree(node.left) && isSumTree(node.right)) {
int leftKey = node.left == null ? 0 : node.left.key;
int rightKey = node.right == null ? 0 : node.right.key;
return (node.key == leftKey + rightKey);
}
return false;
}

public boolean isSumTree() {
return isSumTree(root);
}
}``````

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

``````int FindSum(node * root)
{
if ( root )
{
return (root->val + FindSum( root->left ) + FindSum( root->right ));
}
else
return 0;
}

int isSumTree(node * root)
{
int result = 0; // 0-false, 1-true
if ( root )
{
int nLeftSubTreeSum = FindSum(root->left);
int nRightSubTreeSum = FindSum(root->right);
int nTotalSum = nLeftSubTreeSum + nRightSubTreeSum;
if ( (nTotalSum == root->val) || (nTotalSum == 0) /*leaf node or empty tree*/ )            result = 1;
}
return result;
}``````

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

``````boolean flag = true;

boolean isSumTree(Node rootNode) {
if (rootNode != null) {
int sum = 0;
if (rootNode.leftNode != null) {
sum = rootNode.leftNode.value;
}
if (rootNode.rightNode != null) {
sum = sum + rootNode.rightNode.value;
}
if (rootNode.value == sum) {
if ((rootNode.leftNode.leftNode != null) && (rootNode.leftNode.rightNode != null)) {
isSumTree(rootNode.leftNode);
}
if ((rootNode.rightNode.leftNode != null) && (rootNode.rightNode.rightNode != null)) {
isSumTree(rootNode.rightNode);
}
} else {
flag = false;
return false;
}
}
return flag;
}``````

AnanthaNag KUNDANALA

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

Here's a O(n) solution

``````int issumtree_better(struct node *node)
{
int ls;
int rs;

if(node == NULL || isleaf(node))
return 1;

if(issumtree_better(node -> left) && issumtree_better(node -> right))
{
if(node -> left == NULL)
ls = 0;
else if(isleaf(node -> left))
ls = node -> left -> data;
else
ls = 2 * node -> left -> data;

if(node -> right == NULL)
rs = 0;
else if(isleaf(node -> right))
rs = node -> right -> data;
else
rs = 2 * node -> right -> data;

return node -> data == ls + rs;
}

return 0;
}``````

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.