The input to the Tree Evaluation problem is a binary tree of height $h$ in which each internal vertex is associated with a function mapping pairs of $\ell$-bit strings to $\ell$-bit strings, and each leaf is assigned an $\ell$-bit string.
The desired output is the value of the root, where the value of each internal node is defined by applying the corresponding function to the value of its children.

We provide an exposition and a digest of the recent result of Cook and Mertz ({\em ECCC}, TR23-174), which asserts that Tree Evaluation problem can be solved in space $O((h+\ell)\cdot \log\ell)$.
In particular, we point out that the algebraic manipulation (using roots of unity) performed in the original work is merely a special case of univariate polynomial interpolation.
Using this observation we provide a more transparent exposition of their main result as well as its low order quantitative improvement (i.e., space complexity $O(\ell+h\cdot\log\ell)$).

Our exposition refers to the ``global storage'' model rather than to the ``catalytic storage'' model used by Cook and Mertz, which can be viewed as a special case.
We believe that the global storage model is more flexible and intuitive, but our exposition can be easily adapted to the catalytic storage model.

Most importantly, as pointed out by Ben Chen, the result stated in Theorem 2 was also proved by Cook and Mertz.

In addition, we corrected a few typos.

The input to the Tree Evaluation problem is a binary tree of height $h$ in which each internal vertex is associated with a function mapping pairs of $\ell$-bit strings to $\ell$-bit strings, and each leaf is assigned an $\ell$-bit string.
The desired output is the value of the root, where the value of each internal node is defined by applying the corresponding function to the value of its children.

We provide an exposition and a digest of the recent result of Cook and Mertz ({\em ECCC}, TR23-174), which asserts that Tree Evaluation problem can be solved in space $O((h+\ell)\cdot \log\ell)$.
In particular, we point out that the algebraic manipulation (using roots of unity) performed in the original work is merely a special case of univariate polynomial interpolation.
Using this observation we provide a more transparent exposition of the result as well as a low order quantitative improvement (i.e., we improve the space complexity from $O((\ell+h)\cdot\log\ell)$ to $O(\ell+h\cdot\log\ell)$).

Our exposition refers to the ``global storage'' model rather than to the ``catalytic storage'' model used by Cook and Mertz, which can be viewed as a special case.
We believe that the global storage model is more flexible and intuitive, but our exposition can be easily adapted to the catalytic storage model.