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.

A recent result of Cook and Mertz (ECCC, TR23-174) asserts that the Tree Evaluation problem can be solved in space $O(\ell+h\cdot \log\ell)$, where the input length is $\exp(\Theta(h+\ell))$.
Building on our recent exposition of their result (ECCC, TR24-109), we now obtain an $o((h+\ell)\cdot \log(h+\ell))$ space bound. Specifically, we shave off an $\Theta(\log\log(h+\ell))$ factor.

The improvement is obtained by improving the procedure of Cook and Mertz for a generalized tree evaluation problem that refers to $d$-ary trees. We then reduce the binary case to the $d$-ary case while cutting the height of the tree by a factor of $\log_2d$.

(The main result reported in this memo was obtained by Manuel Stoeckl, a student at Dartmouth, half a year before us.
Manuel felt that this result is a minor observation and did not find the time to write it down.
He also declined our invitation to co-author this memo.)