  A function on an algebra is congruence preserving if, for any congruence, it
maps pairs of congruent elements onto pairs of congruent elements. An algebra
is said to be affine complete if every congruence preserving function is a
polynomial function. We show that the algebra of (possibly empty) binary trees
whose leaves are labeled by letters of an alphabet containing at least one
letter, and the free monoid on an alphabet containing at least two letters are
affine complete.

Rings and Algebras;Formal Languages and Automata Theory