1
$\begingroup$

I have a tree data structure (rooted, unbalanced, with unbounded branching factor), where each individual node has an associated 'weight'. For every node $n$ in the tree, I'd like to compute the cumulative weights of all the nodes in the subtree rooted at node $n$.

For example, in the tree below I'd want to compute the numbers in brackets:

A: 4 (27)
|
+--B: 1 (12)
|  |
|  +--D: 5 (9)
|  |  |
|  |  +--I: 3 (3)
|  |  |
|  |  `--J: 1 (1)
|  |
|  `--E: 2 (2)
|
`--C: 2 (11)
   |
   +--F: 4 (4)
   |
   +--G: 2 (2)
   |
   `--H: 3 (3)

Starting at the root node, how can I compute these whilst visiting each node a minimum number of times?

$\endgroup$
  • $\begingroup$ use postorder traversal and sum the subtree cumulative weights $\endgroup$ – k20 Nov 11 '14 at 17:04
  • $\begingroup$ Can I answer in Lisp? ;) You can probably find more detail to flesh out @k20's suggestion in the books by Sedgewick or Skiena. $\endgroup$ – Daniel Shapero Nov 12 '14 at 1:21
5
$\begingroup$

No need for any advanced books, the easiest to implement answer is:

Use a DFS (http://en.wikipedia.org/wiki/Depth-first_search), and store the cumulative sum of each subtree in the stack.

For example, a possible DFS traversal in your example is: A->B->D->I->J->E->C->F->G->H.

After computing the cumulative sum of the child of a node, add this value to that of the parent. When done computing all the sums of the children nodes, have the parent return its value to its own parent. (e.g. After computing all of B's children, return the value of B to A). Continue until done with tree.

Pseudocode:

int sum(int n)
{
    int cumulative=0;
    for all children i of n
        cumulative+=sum(i)
    cumulative+=value[n]
    return cumulative
}

I apologize for the similarity of the Pseudocode to C++ ;). The complexity is Θ(n), and you can't get any faster, since you must access each node at least once to find the sum/get input (if it exists).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.