# Name for tree where each node has the aggregate of its children

Is there a general name for a tree in which the leaves have some arbitrary values and the value of every other node is some "aggregate" function of its children?

An example where the aggregate function is the sum:

  14
/  \
4   10
/ | \
7  1  2


The function could also be the min, max, or any other function of the form $f:S^n\to S$.

• Whether and how to actually store these values may be an implementation detail from the perspective of classic algorithmics. (Recursive) Functions on trees are just that; I don't know of a special name. – Raphael Oct 4 '17 at 17:41

## 1 Answer

Such tree is called Sum Tree or SumTree, where the property is maintained in bottom up fashion. In general if the value is additional value (node property) for some existing one like AVL it is Sum augmented AVL Tree.

If the property is inherent, like maintaining the prefix sum, it would be Fenwick Tree.

As far as I know there is no established name, but for other functions it is partial statistics tree. preferable name would be Tree augmented with $f$, to make it explicit.