Tree structure category sum that cascades to root node.

Question

Hi All,

I'm going to come right out and say that I am not the worlds greatest Mathematician :D So this problem may well be simple to most of you. Unfortunately it's confusing me and have had several stabs at a workable solutions.

As with any tree, one can have many branches, many branches can have more branches and so forth until they end with a leaf node. I've got information on each leaf that indicates its value.

What I require is a clear explination on how to tackle the problem of summarising each leaf node value as a total for it's branch (parent) and doing the same for the rest but not forgetting that if a branch is shared by other branches that it is the summary of each lower level branch and leaf that is directly related to itself.

To better explain:

Root
|----Branch
|         |-Leaf 10
|----Branch
|         |----Branch
|         |-Leaf 20 |-Leaf 30
|----Branch         |-Leaf 40
|         |----Branch
|                   |----Branch
|                             |----Leaf 50
|-Leaf 60

The goal:

Root 210
|----Branch 10
|         |-Leaf 10
|----Branch 90
|         |----Branch 70
|         |-Leaf 20 |-Leaf 30
|----Branch 50      |-Leaf 40
|         |----Branch 50
|                   |----Branch 50
|                             |----Leaf 50
|-Leaf 60

I am able to identify the lowest level members (leaf nodes), the root node and the branches themselves. I don't have identification on whether or not the branch has other branches linked to itself lower down or directly linked to a leaf node. The relationship is very much bottom upwards to root. IE: The branch has no reference to who it's children are, but the children know who the parent is.

Please if something is unclear ask and I'll try and explain the problem better.

Any help would be appreciated.

Answer 1

You want to determine the sum of all the nodes in the tree?

Tree walking lends itself to an elegant recursive solution:

public int SumTree (TreeNode n) {
    if(n.isLeafNode) return n.value;
    return SumTree(n.left) + SumTree(n.right);
}

Assuming a binary tree.

Answer 2

OK, lefts give this a stab.

I would go about it like this with some pseudo code

foreach leaf in knownLeafs
    parent = leaf.parent //get the leaf parent
    parent.total = parent.total + leaf.value //add leaf value to parent total
    while parent.parent != null //loop until no more parents, this would be the root
    {
     current = parent
     parent = parent.parent //move up the structure
     parent.total = parent.total + current.total
    }
next leaf

you would need to create a function that will, given a node, return the parent node

node GetParentNodeFrom(node)

the new pseudo code would look something like this

foreach leaf in knownLeafs
parent = GetParentNodeFrom(leaf) //get the leaf parent

parent.total = parent.total + leaf.value //add leaf value to parent total
while GetParentNodeFrom(parent) != null //loop until no more parents, this would be the root
{
    current = parent
    parent = GetParentNodeFrom(current) //move up the structure
    parent.total = parent.total + current.total
}
next leaf

Sorry, my mistake, you should only move the leaf value up, not the totals too. See new leafValue used.

foreach leaf in knownLeafs
parent = GetParentNodeFrom(leaf) //get the leaf parent
leafValue = leaf.value
parent.total = parent.total + leafValue //add leaf value to parent total
while GetParentNodeFrom(parent) != null //loop until no more parents, this would be the root
{
    current = parent
    parent = GetParentNodeFrom(current) //move up the structure
    parent.total = parent.total + leafValue
}
next leaf