Replace the node's value to be the sum of all its descendents

private void sumNode(TNode node) {
    int sum = 0;
    if (node == null)
        return;

    sumNode(node.getLeft());
    sumNode(node.getRight());
    if (node.getLeft() != null && node.getRight() != null) {
        sum = (node.getData() + node.getLeft().getData() + node.getRight()
                .getData());
    } else if (node.getLeft() != n开发者_运维知识库ull) {
        sum = (node.getData() + (Integer) node.getLeft().getData());
    } else if (node.getRight() != null) {
        sum = (node.getData() + node.getRight().getData());
    } else {
        sum = 0;
    }
    node.setData(sum);
}

I know my method is totally wrong - I have no idea how to do this.

I want to replace each node value to be the summation of all its descendants, can anyone guide me how to do?

I have ran out ideas for how to solve this problem. Even pseudocode will be appreciated.

The problem is:

• My tree has: 5 2 1 3 6 8
• The outcome is: 0 0 2 0 6 13,
• The expected outcome is: 0 0 4 0 8 20

If you want to include the original value of the node in the sum, then this is very easy with recursion:

public void sumNode(TNode<E> root) {
    // For empty trees, do nothing.
    if (root == null)
        return;

    // Update the left subtree recursively.
    sumNode(root.left);

    // Update the right subtree recursively.
    sumNode(root.right);

    // At this point, all the elements in the left and right
    // subtrees are already summed up. Now we update the
    // sum in the root element itself.
    if (root.left != null)
        root.item += root.left.item;
    if (root.right != null)
        root.item += root.right.item;
}

If you do not want to include the original value, then a single recursive pass is not enough because by the time you calculate the value of a non-leaf node N with two leaves L1 and L2, the values in L1 and L2 have already been updated to zeros, so you cannot use the original values of L1 and L2 to store N. If you are allowed to add a new originalItem entry in the node, you can store the original value there, use my solution above and then run a final pass which subtracts the value of originalItem from item for every node in the tree:

private void preprocessTree(TNode<E> root) {
    if (root == null)
        return;

    preprocessTree(root.left);
    preprocessTree(root.right);
    root.originalItem = root.item;
}

private void processTree(TNode<E> root) {
    if (root == null)
        return;

    processTree(root.left);
    processTree(root.right);
    if (root.left != null)
        root.item += root.left.item;
    if (root.right != null)
        root.item += root.right.item;
}

private void postprocessTree(TNode<E> root) {
    if (root == null)
        return;

    postprocessTree(root.left);
    postprocessTree(root.right);
    root.item -= root.originalItem;
}

public void sumTree(TNode<E> root) {
    preprocessTree(root);
    processTree(root);
    postprocessTree(root);
}

Not sure if i am getting the problem correctly given the complexity of the most accepted answer from Tamas but the following simpler code seems to work for me(correct me if i am missing a test case):

1) If you have to "exclude" the current nodes value from the sum the use following:

public static int sumDesc(TreeNode root)
{
    if(root == null) return 0;

    int temp = root.data;

    root.data = sumDesc(root.leftChild)+ sumDesc(root.rightChild);

    return root.data+temp;
}

2) If you have to "include" the current nodes value then use following:

public static int sumDescInc(TreeNode root)
{
    if(root == null) return 0;

    root.data += sumDescInc(root.leftChild)+ sumDescInc(root.rightChild);

    return root.data;
}

To store the sum of all descendants in the Node couples your node/tree very closely to a specific job. Wouldn't it then be better, to have the traversing and summing method in the TNode-class? Where is it now?

Another question: If you need to recalc the tree, you have to traverse the whole tree again, or you have to know, whether you already calculated the sum, and no modification of values or tree happened since then. But wouldn't it be more easy then, to calculate the sum as soon as you insert a node, so that the tree always reflects the sums? Is the data of each TNode final? Hm - it can't, if it first is the nodes own value, and later the value of the node plus all descendants.

I have not really tested this, but I think something like this should work to help get the sum of the nodes children. Then you can go through and replace each nodes value with this sum.

public int sum(Node node){
  return (!node.isLeaf()) ? sum(node.getLeftChild())+sum(node.getRightChild()) : node.getValue();
}

this code serves the purpose where the original data of left and right sub tree is added which is stored in the corresponding node (pure recursive way)

int sumofnodes(Node **root)
{
    if(*root==NULL)
        return 0;
    if((*root)->left==NULL && (*root)->right==NULL)
    {
        int temp=(*root)->val;
        (*root)->val=0;
        return temp;
    }
    int sum=sumofnodes(&(*root)->left)+sumofnodes(&(*root)->right);
    int data=(*root)->val;
    (*root)->val=sum;
    return (data+sum);


}

I think this maybe a simple solution:

package tree;
import java.util.ArrayList;

public class TreeNode<T> {
    T data;
    ArrayList<TreeNode<T>> children;
    //generics don't make array
    public TreeNode(){
        children = new ArrayList<TreeNode<T>>(); 
    }
}

public static int sum(TreeNode<Integer> root)
{
        int s1=root.data;
        for(int i=0;i<root.children.size();i++)
            s1+=sum(root.children.get(i));

        return s1;          

}

Simple solution with recursion.

int sumNode(Node *root) {
    // For empty trees, return 0.
    if (root == null)
        return 0;
    // For leaf node return its value
    if(root->left==NULL && root->right==NULL)
        return root->data;

    //calculate left subtree sum recursively
    int LST=sumNode(root->left)

    //Calculate right subtree sum recursively
    int RST=sumNode(root->right)

    // store the value of root for its parent
    int temp=root->data;

    // store the result
    root->data = LST+RST;
    return temp+LST+RST;
}