Class invariants characterize valid object states throughout an object’s lifecycle and play an important role for software maintenance and evolution. Because invariants are rarely documented, software engineers resort to modern data-driven techniques for their inference. Recent automatic techniques require representative sets of invalid objects as negative training examples, which are hard to come by for programs with reference-based data structures such as search trees. For example, techniques adopting program mutation invalidate search tree objects well wrt. their payload, but they fail to introduce cycles, despite acyclicity being an important property of trees. In this paper, we analyze the limitations of program mutation for constructing invalid objects and propose state mutation as a complementary approach. Our approach first retrieves valid objects from program executions and then systematically mutates object references to obtain structurally invalid objects. An evaluation on a benchmark of diverse reference-based data structures shows that, unlike program mutation, state mutation effectively generates invalid objects with structural violations. Moreover, combining both approaches significantly outperforms either one and delivers diverse negative training examples that capture more facets of a given data structure, thereby permitting the inference of more precise class invariants.