Amazon Interview Question
Country: India
bool isSumTree(node* head)
{
if( head == NULL )
return true;
int rightValue = 0, leftValue = 0;
if(head->right != NULL)
rightValue = head->right->data;
if(head->left != NULL)
leftValue = head->left->data;
if( leftValue + rightValue != headValue)
return false;
else
return isSumTree(head->right)&&isSumTree(head->left);
}
why not take
static int rightValue, leftValue;
rightValue = 0;
leftValue = 0;
It will save stack while recursion.
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));
}
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);
}
}
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;
}
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
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;
}
bool isSumTree(node* head)
- Wayne December 22, 2011