Tree Evaluation was considered to be a candidate problem solvable in polynomial time but not in log space. The natural algorithm for performing tree evaluation takes roughly log^2(n) space and was conjectured to be optimal. The belief was based on an assumption that space being used for storing old values cannot be used for new computation. Cook and Mertz showed this assumption to be false, in earlier work. In this paper, they improve the space complexity to O(log n . log log n) using similar strategy of reusing space being used for storing old values without erasing it.
