Abstract Recent results have shown the interest of trees-ofBDDs [Subbarayan et al., 2007] as a suitable target language for propositional knowledge compilation from the practical side. In the present paper, the concept of tree-of-BDDs is extended to additional classes of data structures C thus leading to trees-of-C representations (ToC). We provide a number of generic results enabling one to determine the queries/transformations satisfified by ToC depending on those satisfified by C. We also present some results about the spatial effificiency of the ToC languages. Focusing on the ToOBDD< language (and other related languages), we address a number of issues that remained open in [Subbarayan et al., 2007]. We show that beyond CO and VA, the ToOBDD< fragment satisfifies IM and ME but satisfifies neither CD nor any query among CE, SE unless P = NP. Among other results, we prove that ToOBDD< is not comparable w.r.t. succinctness with any of CNF, DNF, DNNF unless the polynomial hierarchy collapses. This contributes to the explanation of some empirical results reported in [Subbarayan et al., 2007]