SHEETS: How do you sum children recursively into a parent row?

user_5297926 0
Viewed 53

I have a simple google sheet where each row represents a node in a tree that holds a reference to its parent and some descriptor values about it. I would like to have a column that sums the child nodes beneath the current one.

e.g:

Node ID, Parent Node ID, Minimum Value, Self Value, Total Value
1, 0, 30, 10, 90
2, 1, 10, 20, 40
3, 1, 10, 20, 40
4, 2, 1, 10, 10
5, 3, 1, 10, 10
6, 3, 1, 10, 10
7, 2, 1, 10, 10

Where Self Value is statically defined, and Total Value represents Self Value + SUM(CHILDREN.Total Value). Do I need to re-organize the sheet to accomplish this or am I missing the proper way to recursively sum-up the child rows?

google-sheets-formula
1 Answers

Introduction

tl,dr: this method works but is impractical for large complex datasets.

This seems to be rather complicated for what Sheets or similar software are designed, I'm think it would be probably much easier to solve in Apps Script (where I have no experience) or any other scripting language outside of Sheets.

Meanwhile I have come up with solution that works using only formulas in Sheets. It has some limitations however: the two formulas have to be manually extended (details below), and it would be cumbersome to use for a very large depth of the dataset (by depth I mean the maximal amount of generations of children nodes).

I have reorganized the columns in your example dataset to make this easier to understand and added two more rows to test it better. I have removed the Minimum Value column, as per your question, it is not relevant to the expected results.

SelfValue NodeID Parent
10 1 0
20 2 1
20 3 1
10 4 2
10 5 3
10 6 3
10 7 2
5 8 7
5 9 8

Solution and explanation

My main idea was that it is relatively easy to calculate Total Value of a given node if we know its children in all generations (not just its immediate children, but also "grandchildren" and so on) and their Self Value. In particular, to know Total Value of a node, we do not need to have explicitly calculated the Total Value of its immediate children.

I have not found a simple way to enumerate children from all generations for a given node. I have approached it by finding the parents of the parents, and so on, for all nodes instead. To do this, I have entered the following formula in D2 and then manually extended this formula across the next columns up to column H (the first column to show only empty values):

=ARRAYFORMULA(IFERROR(VLOOKUP(C2:C,$B$2:$C,2,false)))

I attempted to make it automatically fill multiple columns without manually extending, but this gave me the circular dependence error.

The next and final step is to calculate the Total Value of all nodes, now that we have a way to identify all of their children (in all generations). I entered the following formula in cell I2 and then manually extended it down across all rows:

=IFERROR(SUM(FILTER(A$2:A,BYROW(B$2:H,LAMBDA(row,NOT(ISERROR(MATCH(B2,row,0))))))))

This calculates the Total Value by adding Self Value of all nodes, for which the given node is parent (in any generation) and the Self Value of the given node itself. The range B$2:H has to be adapted, if the dataset is deeper and there are more columns filled with the first formula.

Here is the final result, I have colorized the cells where the two formulas are entered (green, yellow) and extended (light green, light yellow):

Sheet with final result

It seems it would be more efficient (less calculations in the background, more responsive sheet) by using QUERY, but then all the columns C-H need to be explicitly listed like select sum(A) where B="&B2&" or C="&B2&" or ..., so it becomes a problem in itself to construct this formula and adapt to a variable number of columns from the previous step.

I attempted to make the formula automatically fill all rows (instead of manually expanding) by experimenting with ARRAYFORMULA or MAP(LAMBDA), but it either didn't work or exceeded the calculation limit.

Anyway it would be interesting to see if there is another simpler solution to it using only formulas. Also it surely can be done more efficiently and elegantly using Apps Script.

user_200146330
Related