title: Sum a tree, with values in leaf nodes and subtotal in parent, up to root
body: <p>Is there a readily available solution to sum all leaf nodes of an n-ary tree, and assign the sum to their parent node all the way up to the root?</p>
  
  <p>Let me explain. I have several reports which I receive weekly. It's a financial document which is essentially an unbalanced hierarchical dataset up to nine-levels deep. Values are assigned only at the last level, but each parent has a sum of it's children (ie. only 1 edge away). </p>
  
  <p>It looks something like:</p>
  
  <pre><code>root:
      sectionA:
          sectionB:
              sectionC:
                  sectionD:
                      subtotal sectionE = sum of x 
                          leaf-1 = x_1
                          leaf-2 = x_2
                          leaf-n = x_n
  </code></pre>
  
  <p>I'm working to automate the validation on this dataset. I need to sum each leaf and determine if it matches it's <strong>parent-subtotal</strong> all the way up to  the <strong>root-total</strong>.</p>
  
  <p>Also, I have a second table listing all of the leaf-elements together with their the parent relations. Something like this:</p>
  
  <pre><code>root:sectionA:sectionB:sectionC:sectionD:sectionE:leaf
  </code></pre>
  
  <p>I'm thinking a k-ary tree could represent the correct report structure generated from table #2. Then use the tree to compare to the weekly reports. I like this direction because the second table has structural data in this form (the full parent-path). Further down the road, when my script is complete, I will need to generalize the solution. </p>
  
  <p>Is there a Python module or generalizable algorithm that addresses this problem? </p>
  
  <p>Here's an example solution, <a href="https://www.geeksforgeeks.org/sum-elements-n-ary-tree/" rel="nofollow noreferrer">Sum of all elements of N-ary Tree</a>. But this solution assumes each node has a unique value, and edges are just relations. </p>