13,097,884 members (56,445 online)
Rate this:
See more:
Hi everyone,

I have a hierarchical tree that can have an unspecified number of branches. You add children to parents then parents to their parents and so on. Everything then gets added onto the main branch. Something like this:
```MyTree t = new MyTree();
Branch topBranch = new Branch();
Branch B1 = new Branch(topBranch);
Branch B2 = new Branch(topBranch);
Branch B3 = new Branch(topBranch);
Branch B4 = new Branch(topBranch);
Branch B11 = new Branch(B1);
Branch B21 = new Branch(B2);
Branch B211 = new Branch(B21);
Branch B31 = new Branch(B3);
Branch B41 = new Branch(B4);
t.MainBranch = topBranch;
return t;```

I need to create two functions within MyTree that will assign values to POT and POP attributes of each tree. POT - Percent of Total, POP - Percent of Parent.

I am thinking I probably need to make these functions recursive, however, I have a problem in the function below
CORRECTION HERE:

- when I do
`foreach (Branch b in this.Children)`
, it starts going down the hierarchy - but then I need it to come back up in order to process the siblings. I need help figuring out that part. So Branch 1.1 has a sub branch 1.1.1, but it also has a sibling - Branch 1.2, which has a sub branch 1.2.1. These methods will only process 1.1 and 1.1.1

```private void evaluatePOT(Branch Branch, int runningTotal)
{
if (Branch.POT == 0)
{
runningTotal += 1;

foreach (Branch br in Branch.Children)
{
evaluatePOT(br, runningTotal);
}
Branch.POT = (double)runningTotal / this.TotalNumberOfBranches * 100;
}
else
//get sibling
{
Branch sibling = this.getSibling(Branch);
if (sibling == null)
//if sibling is null then get parent
sibling = Branch.Parent;

evaluatePOT(sibling, runningTotal);
}
}```

```private void evaluatePOP(Branch Branch)
{
if (Branch != null)
{
int totalOtherChildren = 1;

if (Branch.Parent != null)
foreach (Branch B in Branch.Parent.Children)
if (B.Guid != Branch.Guid)
totalOtherChildren += 1;

Branch.POP = (double)1 / totalOtherChildren * 100;
foreach (Branch b in Branch.Children)
evaluatePOP(b);
}
}```
Posted 22-Jun-11 12:06pm
Updated 23-Jun-11 9:52am
v3
Firo Atrum Ventus 22-Jun-11 21:49pm

Like, The rules in assigning their values?
Mesrop Simonian 23-Jun-11 15:54pm

% of total equals The current branch + all of its children / total * 100, % of Parent is same with regards to the parent only instead of the big total.
2irfanshaikh 23-Jun-11 1:03am

If your data is in SQL Server you can use CTE query to do Recursive calculation.

http://msdn.microsoft.com/en-us/library/ms186243.aspx
Mesrop Simonian 23-Jun-11 15:55pm

thanks, but my tree is built inside the code itself, although subsequently it will be in the database... but right now, i need it to work without a backend.

Rate this:

## Solution 1

It's pretty simple: the `runningTotal `is passed to the routine by value, not buy reference. So when you make changes to it, they are not reflected back up the tree.
For example:

```void Change (int i)
{
Console.WriteLine(i);
if (i < 3)
{
i++;
Change(i);
Console.WriteLine("After Change: " + i.ToString());
}
}```

If you call Change with zero, you will get:
```0
1
2
3
After Change: 3
After Change: 2
After Change: 1```
Because after each Change returns, the value if i is reset.
Either return the new value of `runningTotal` when you exit `evaluatePOT`, or make it a `ref` parameter
Mesrop Simonian 23-Jun-11 15:46pm

Thanks for the answer, but I completely screwed up the question. Maybe you'll be up for this challenge as well - the problem isn't that children of children are not being processed, they are. The problem is coming back up in the hierarchy and navigating to siblings, so that ALL branches end up getting processed through the method. Because right now it goes down the list as long as children have children, but then it stops, so if the main branch had 2 subbranches, only the children of the first sub branch are visited, then the execution ends. Sorry for the confusion, I myself wasn't sure exactly why the calculations were wrong.
TRK3 23-Jun-11 16:59pm

Do you have a single root node that is the parent of everything, or do you have several nodes at the top that are "siblings" but have no parent.

If the latter is the case, note that evaluatePOT only traverses either the children or the siblings, but not both, so if the initial node that you call it with has both children and siblings, only the children get evaluated.
Mesrop Simonian 23-Jun-11 18:15pm

single root node that is the parent of everything.
TRK3 23-Jun-11 18:24pm

Are you calling evaluatePOT() on the single root node?

Because if you are, it looks to me like the whole tree is being traversed, but you are only getting the results for the single branch (as per OriginalGriff's solution).

However, you are setting branch.POT when you visit that branch -- but you don't know the full total until you've visited all the branches. So you are using an incomplete value of runningTotal when you set POT. You'll need to traverse the whole tree once to get the total before you can set POT in each branch.
Mesrop Simonian 23-Jun-11 18:41pm

I'm calling it in the Tree object's MainRoot property's set method, so it's supposed to scan all the roots contained within MainRoot and assign the POT and POP properties for each root.
Mesrop Simonian 23-Jun-11 18:42pm

MainBranch I meant to say
TRK3 23-Jun-11 18:45pm

The problem is that you are setting POT using an incomplete value for the total.
Mesrop Simonian 23-Jun-11 18:41pm

Main Branch I meant to say
Rate this:

## Solution 2

See my reply in Solution 1 for why root level siblings are not getting traversed.

I think a better way to do this, would be to have a member variable called TotalNumberOfChildren.

When you create a branch, TotalNumberOfChildren is set to zero.

```void IncrementChildren(int number_added) {
if (this.parent)
}```

In the Add(Branch b) function, call IncrementChildren(b.TotalNumberOfChildren + 1) when you add a child.

(If you implement removeChild() you'll have to implement DecrementChildren() similarly.)

Doing it that way, the TotalNumberOfChildren field will be valid at all times.

Then if you need POP, it's just:
```float POP() {
if (this.parent) {
// POP is total of my children + 1 (self) divided by parent's total.
return (this.TotalNumberOfChildren + 1) * 100.0 /
this.parent.TotalNumberOfChildren;
} else {
return 100.0;  // or Inf or whatever makes sense for POP of the root.
}
}```

And of course, POT is just:

```(this.TotalOfChildren + 1) * 100.0 / root.TotalOfChildren
```

Depending on how you want to use POT, child nodes can traverse all the parent pointers to get to root in order to report POT, or the caller who wants to know POT can be required to have access to root and do the calculation himself given TotalOfChildren.
v3
Mesrop Simonian 23-Jun-11 18:14pm

This solution unfortunately won't work because root.TotalOfChildren cannot be evaluated without recursive calls. When a branch is added, total number of children is incremented only by 1. However, the added branch may have a number of children of its own (say 10), which should be accounted for in the POT evaluation. In this case, the calculated POT for the main branch that contains the entire tree will be 1 (me) + 1 (my children) over 12 (total number of branches) = 16%, which is incorrect if all 10 children are part of the parent's child. The right solution must come out to 12/12 * 100 = 100%. I really don't think this problem will be solvable without recursive calls to the evaluation methods both for POT as well as POP.
TRK3 23-Jun-11 18:22pm

Really? How silly of me.

See my improved solution above.

Of course it can't be solved without recursion -- it's just a matter of deciding where and when to do the recursion.

My proposed solution does the recursion up the parent link when you add, as opposed to doing the recursion down all the children links when you want to calculate POT and POP. Depending on your usage pattern one or the other method is going to be preferrable.
Mesrop Simonian 23-Jun-11 18:49pm

Bottom up vs top-down doesn't matter I think. The question is the ability to do horizontal navigation as well - we got the up/down we need the left/right, so instead of a depth-first search, it needs to be a breadth-first search, but in that case I don't know how to ensure that every single branch in the structure will be visited.
TRK3 23-Jun-11 18:59pm

I don't see why you need to do breadth-first vs. depth-first. For any given node, don't you just need to know the total of all children below that, and the total of all children?

You can count them either depth first, or breadth-first you'll get the same answer.

Of course if you go bottom-up, there isn't any breadth-first / depth-first decision to make -- there is only one up.

That's an advantage of my proposal, you don't have to loop over all children and/or siblings and recurse down them -- just go up the parent links updating the TotalOfChildren. And if you were worried about stack depth, you could always implement that as a loop over the parent links, and update the TotalOfChildren value directly, so that you aren't actually using recursion at all (but the recursive implementation is clearer).

Mesrop Simonian 23-Jun-11 19:36pm

Absolutely. You may be on to something here, because I think you have a partial solution for POP, but POT is still a different issue. I compared the edited solution to the previous version and I only saw differences in the IncrementChildren section. So this IncrementChildren method, I assume, is on branch level, not tree level. If so, where are POP and POT? Branch level or tree level? POP can be branch level and this solution might work, but POT cannot, because "root" is not known at branch level (out of scope). And if that's the case the solution is not implementable. Do you see why?
TRK3 23-Jun-11 20:07pm

Actually root is known at branch level. Every branch knows it's parent, so you can recurse on parent to get root. In other words:

Branch::Root() {
if (this.parent == NULL)
return this;
else
return this.parent.root();
}

Or walk the parent link a loop if you want to avoid recursion.

So POT becomes:

(this.TotalOfChildren + 1) * 100.0 / this.root().TotalOfChildren

If that's efficient enough for what you are doing, your done. My solution for POP is complete, and with the addition of root(), POT is complete as well.
TRK3 23-Jun-11 20:27pm

If for efficiency reasons you don't want to recurse to find root everytime you want POT, then you have a choice:

a) The caller will have to know about root and supply total as an additional argument to POT (not an unreasonable design decision).

b) When you are done adding to the tree you'll have to traverse the whole tree and set POT when the total of the tree is known.
Mesrop Simonian 24-Jun-11 13:09pm

Now that definitely looks like it would work. I'm going to try it now.
Rate this:

## Solution 3

I think this is easiest in two passes (which has been alluded to in previous answers), a precalculation pass where the totals for each node are recorded (which must traverse the whole tree), and a calculation pass where the branch's value is compared to the parent or root.

```class Branch {
int total;
List<Branch> children;
Branch parent;

Branch Root {
get {
Branch b = this;
while(b.parent != null) b = b.parent;
return b;
}
}

int SetNewTotal() {
// Precalculation pass. Traverses the tree (similar to recursion)
int r = 1;
foreach(Branch cb in children) r += cb.SetNewTotal();
}

float POP { get { return total * 1f / parent.total; } }
float POT { get { return total * 1f / Root.total; } }
}```

Whenever you modify the tree you should call rootNode.SetNewTotal to repair all the total values.
v3
Mesrop Simonian 24-Jun-11 13:08pm

the SetNewTotal method always returns 0s... also, isn't total at some point supposed to be assigned the value of r?
BobJanova 24-Jun-11 17:17pm

Whoops, you are correct. That's what I get for writing in a hurry at work ;). Will update the solution.

Top Experts
Last 24hrsThis month
 Graeme_Grant 245 ProgramFOX 115 RickZeeland 105 ppolymorphe 85 Jochen Arndt 65
 OriginalGriff 4,219 Graeme_Grant 2,412 ProgramFOX 2,117 Jochen Arndt 1,860 ppolymorphe 1,820