Algorithm to aggregate values from child tree nodes

Question

I have objects in a tree structure, I would like to aggregate status information from children nodes and update parent node with aggregated status. Lets say node A has children B1, B2, and B1 has C1, C2, C3 as children. Each of the nodes have a status attribute.

Now if C1, C2, C3 are all complete then I would like to mark B1 as completed. And if C4, C5,C6,C7 are complete make B2 as complete. When B1 and B2 are both complete mark A as complete.

I can go through these nodes in brute force method and make updates, could someone suggest an efficient algorithm to do it.

A { B1 { C1, C2, C3}, B2 { C4, C5, C6, C7} }

Answer 1

You need post-order traversal - first visit the children of a node, then mark the node itself, recursively.

Something like (pseudocode):

iscomplete(node):
  if node == Null:
     return False
  elsif no children:
     return some "complete" value according to node value
  else:
     for child in node.children:
         if not iscomplete(child):
             return False

  return True

Answer 2

I can't see that you can evade "brute force".

I would use the visitor design pattern.

http://www.javaworld.com/javaworld/javatips/jw-javatip98.html

http://sourcemaking.com/design_patterns/visitor

Answer 3

Eli Bendersky has it right, the general answer to this problem is post-order traversal.

For more efficiency, though, you have to use everything you know about the problem. For example, if you can allow some "staleness" then it might be better to cache a complete flag and a timestamp in each node.

Another possibility is that the internal complete status of nodes rarely changes. In this case, it might be much better to propagate up completeness information. Something like that:

class NodeWithCompletenessInfo : public Node {

  private bool internalComplete; // Am I personally done?
  private bool childrenComplete; // Are my children done?

  public bool isComplete() {
    return internalComplete && childrenComplete;
  }

  public void markComplete() {
    internalComplete = true;
    if( isComplete() )
      parent.markChildComplete();
  }

  public void markIncomplete() {
    if( isComplete() )
      parent.markChildIncomplete();
    internalComplete = false;
  }

  private void markChildComplete() {
    for( child in children ) {
      if( !child.isComplete() )
        return;
      childrenComplete = true;
    }
    if( isComplete() )
      parent.markChildComplete()
  }

  private void markChildIncomplete() {
    if( isComplete() )
      parent.markChildIncomplete();
    this.childrenComplete = false;
  }
}

Answer 4

If you know which are leaf nodes then

 A { 
    B1 
        {C1, C2 = false, C3},
    B2 
        {C4, C5=false, C6=false, C7} 
  } // those not marked false are true ;)

not_complete_leaf_nodes_with_different_parents = [ C2 , C5]

mark_not_complete(node):
    node.complete = false
    if parent != null
        mark_not_complete(node.parent)

for each in not_complete_leaf_nodes_with_different_parents:
    mark_not_complete(each.parent)