Combinatorial or “$t$-way” testing provides a principled way of testing the possible behaviors of a system. While this approach is well studied for systems that operate on simple input parameters, there has been relatively little exploration of its use for more complex structured data. We propose a definition of $t$-way testing that is generalized to algebraic data types, including recursive types. We define combinatorial coverage using regular tree expressions as descriptions of tests, and we provide a sketch of an algorithm for generating covering test sets that are guaranteed to catch certain classes of bugs. This abstract presents work in progress.