In this paper, we propose an extension of finite state tree automaton, called tree automaton with tree memory (TTA), and also define structure composing TTA (SC-TTA) and backward deterministic TTA (BD-TTA) as subclasses of TTA. We show that the classes of yield languages accepted by TTAs, SC-TTAs and BD-TTAs are equal to the class of recursively enumerable languages, the class of languages generated by tree-to-string finite state translation systems (TSFSTSs) and the class of languages generated by deterministic TSFSTSs, respectively. As a corollary, it is shown that the yield language accepted by an SC-TTA (resp. a BD-TTA) is linear space (resp. polynomial time) recognizable.