CareerCup

Do a post order traversal of the linked list and when the node is processed sumup the left , right and root node.

bool isLeaf(Node *n)
{
if (n == NULL);
return false;

if (n->left == NULL && n->right == NULL)
return true;
else
return false;
}
update2SumTree(Node *n)
{
if (n == NULL)
return;
update2SumTree(n->left);
update2SumTree(n->right);

int sum_left = 0;
if (n->left)
{
if(isLeaf(n->left))
sum_left = n->left->data;
else
sum_left = 2 * (n->left-data);

}

int sum_right = 0;
if (n->right)
{
if(isLeaf(n->right))
sum_right = n->right->data;
else
sum_right = 2 *(n->right->data);
}

n->data = sum_right + sum_left;
}

Assuming only leaf nodes have values:

int UpdateTree(Node* n) {
    if(n==NULL) return 0; // check if the pointer is NULL, this is needed
                          // if the root is NULL, or if a node has only 1
                          // child and we call this function on both
                          // children of that node. see below.
    if(n->left || n->right) // if at least one child exists,
                            // update the value of the current node.
        n->data = UpdateTree(n->left)+UpdateTree(n->right);
    return n->data;
}

If internal nodes also have values that need to be summed with the subtrees, we don't need to check if at least one child exists. We can just add the values.

int UpdateTree(Node* n) {
    if(n==NULL) return 0;
    n->data += UpdateTree(n->left)+UpdateTree(n->right);
    return n->data;
}

It's either I understand the question wrong or you code is incorrect

can we have an iterative solution for this?

What is the space complexity of this code?

3                              24        
                  /    \                          /     \
                2      4                     3        18
             /          /   \                 /          /   \
          1          6     8      =>  1          6   8

Is this correct example ?

//Gets the sum of children given the root node.
int Sum(Node* root)
{
if(root== NULL ) return 0;
return Sum(root->llink) + root->data + Sum(root->rlink);
}
//Gets the sum of children of every node.
int SumNode(Node* root)
{
if(root == NULL) return 0;

root->data = Sum(root->llink) + Sum(root->rlink);

SumNode(root->llink);
SumNode(root->rlink);
}

sujith : your solution is O(n2) complexity. can we get this in O(n) ?

public static int sum(BSTree t) {
if(t.leftChild!=null && t.rightChild!=null)
t.value = sum(t.leftChild)+sum(t.rightChild);
if(t.leftChild!=null && t.rightChild==null)
t.value = sum(t.leftChild);
if(t.rightChild!=null && t.leftChild==null)
t.value = sum(t.rightChild);

return t.value;
}

I think this might work ....

This will help..
int sum(struct node * head)
{int a,b,temp;
if(head==null)
return 0;
if(head->left==null && head->right==null)
{temp=head->data
head->data=0;
return temp;
}
temp=head->data;
a=sum(head->left);
b=sum(head->right);
head->data=a+b;
return(a+b+temp);
}

int SumNode(NODE *root)
{
if(root == NULL) return 0;
else
return (root->data = sumnode(root->llink) + root->data + sumnode(root->rlink));
}

int update(node *x)
{
    if (!x)
        return 0;
    return x->inf += (update(x->left) + update(x->right));
}

int update(node *x)
{
int data;
if (!x)
return 0;
data = x->inf;
x->inf += (update(x->left) + update(x->right));
return (data);
}