Leaf Complexity and Nonno Cedro

Tree data appears in many different contexts: from the syntax analysis of sentences to the parsing of mathematical expressions. Generally any recursive algorithm can generate data in tree form. Then a question naturally arises: how to measure tree complexity?

Clearly the number of tree nodes (root, parents and leaves) is a simple measure of complexity. However, if the leaves are numeric, a sometimes more natural complexity measure is their total. More generally one may think to define a custom complexity function applied to all leaves, and then sum it, or multiply it, or wrap it with any other function.

All these tree complexity measure definitions have just been implemented in the new computational construct “Leaf Complexity”. Notwithstanding its simplicity, this function already seems surprisingly useful to better simplify certain algebraic expressions or select the simplest closed forms.

Both the original curated Wolfram Language version and its faithful Python port are already available:

ResourceFunction[“LeafComplexity”]

pip install leaf-complexity

Interesting benchmarks are also available on GitHub: with the exact same algorithm Wolfram interpreted code performs about 2.5x faster than the SymPy analogue.

The contributor and maintainer Daniele Gregori would like to dedicate this simple but beautiful algorithm to the old tree — “Nonno Cedro” — of his family garden, which unfortunately recently has been nearly destroyed by an extreme weather event.