Applications in many domains are based on a series of traversals of tree
structures, and {\em fusing} these traversals together to reduce the total number
of passes over the tree is a common, important optimization technique. In
applications such as compilers and render trees, these trees are heterogeneous:
different nodes of the tree have different types. Unfortunately, prior work for
fusing traversals falls short in different ways: they do not handle heterogeneity;
they require using domain-specific languages to express an application; they rely
on the programmer to aver that fusing traversals is safe, without any soundness
guarantee; or they can only perform coarse-grain fusion, leading to missed fusion
opportunities. This paper addresses these shortcomings to build a framework for
fusing traversals of heterogeneous trees that is automatic, sound, and
fine-grained. We show across several case studies that our approach is able to allow
programmers to write simple, intuitive traversals, and then automatically fuse
them to substantially improve performance.