Sum up child values and save the values calculated in intermediate steps

struct node { 
    int value; 
    struct node* left; 
    struct node* right; 
    int left_sum;
    int right_sum;
} 

In a binary tree, from a particular node, there is a simply recursive algorithm to sum up all its child values. Is there a way to save the values calculated in the intermediate steps and store them as left_sum and right_sum in child nodes?

Will it be easier to d开发者_Go百科o this bottom up by adding a struct node* parent link to the node definition?

No, this is clearly an exercise in recursion. Think about what the sum means. It's zero plus the "sum of all values from the root down".

Interestingly enough, the "sum of all values from the root down" is the value of the root node plus the "sum of all values from its left node down" plus the "sum of all values from its right node down".

Hopefully, you can see where I'm going here.

The essence of recursion is to define an operation in terms of similar, simpler, operations with a terminating condition.

The terminating condition, in this case, is the leaf nodes of the tree or, to make the code simpler, beyond the leaf nodes.

Examine the following pseudo-code:

def sumAllNodes (node):
    if node == NULL:
        return 0
    return node.value + sumAllNodes (node.left) + sumAllNodes (node.right)

fullSum = sumAllNodes (rootnode)

That's really all there is to it. With the following tree:

           __A(9)__
          /        \
      B(3)          C(2)
     /    \             \
D(21)      E(7)          F(1)

Using the pseudo-code, the sum is the value of A (9) plus the sums of the left and right subtrees.

The left subtree of A is the value of B (3) plus the sums of its left and right subtrees.

The left subtree of B is the value of D (21) plus the sums of its left and right subtrees.

The left subtree of D is the value of NULL (0).

Later on, the right subtree of A is the value of C (2) plus the sums of its left and right subtrees, it's left subtree being empty, its right subtree being F (1).

Because you're doing this recursively, you don't explicitly ever walk your way up the tree. It's the fact that the recursive calls are returning with the summed values which gives that ability. In other words, it happens under the covers.

And the other part of your question is not really useful though, of course, there may be unstated requirements that I'm not taking into account, because they're, well, ... unstated :-)

Is there a way to save the values calculated in the intermediate steps and store them as left_sum and right_sum in child nodes?

You never actually re-use the sums for a given sub-tree. During a sum calculation, you would calculate the B-and-below subtree only once as part of adding it to A and the C-and-below subtree.

You could store those values so that B contained both the value and the two sums (left and right) - this would mean that every change to the tree would have to propagate itself up to the root as well but it's doable.

Now there are some situations where that may be useful. For example, if the tree itself changes very rarely but you want the sum very frequently, it makes sense performance wise to do it on update so that the cost is amortised across lots of reads.

I sometimes use this method with databases (which are mostly read far more often than written) but it's unusual to see it in "normal" binary trees.

Another possible optimisation: just maintain the sum as a separate variable in the tree object. Initialise it to zero then, whenever you add a node, add its value to the sum.

When you delete a node, subtract its value from the sum. That gives you your very fast O(1) "return sum" function without having to propagate upwards on update.

The downside is that you only have a sum for the tree as a whole but I'm having a hard time coming up with a valid use case for needing the sum of subtrees. If you have such a use case, then I'd go for something like:

def updateAllNodes (node):
    if node == NULL:
        return 0
    node.leftSum = updateAllNodes (node.left)
    node.rightSum = updateAllNodes (node.right)
    return node.value + node.leftSum + node.rightSum

change the tree somehow (possibly many times)
fullSum = updateAllNodes (root)

In other words, just update the entire tree after each change (or batch the changes then update if you know there's quite a few changes happening). This will probably be a little simpler than trying to do it as part of the tree update itself.

You can even use a separate dirtyFlag which is set to true whenever the tree changes and set to false whenever you calculate and store the sum. Then use that in the sum calculation code to only do the recalc if it's dirty (in other words, a cache of the sums).

That way, code like:

fullSum = updateAllNodes (root)
fullSum = updateAllNodes (root)
fullSum = updateAllNodes (root)
fullSum = updateAllNodes (root)
fullSum = updateAllNodes (root)

will only incur a cost on the first invocation. The other four should be blindingly fast since the sum is cached.