John,
If I use zippers, do all my nodes need to be the same type?
No, zippers can also be defined for mutually recursive data types. In a paper to be presented at ICFP, next September, Alexey Rodriguez, Andres Löh, Johan Jeuring, and I show how zippers for mutually recursive data types can be derived in Haskell: Alexey Rodriguez, Stefan Holdermans, Andres Löh, and Johan Jeuring. Generic programming with fixed points for mutually recursive datatypes, 2009. To appear in the proceedings of the 14th ACM SIGPLAN International Conference on Functional Programming, ICFP 2009, Edinburgh, Scotland, August 31–September 2, 2009. http://people.cs.uu.nl/stefan/pubs/rodriguez09generic.html . An implementation is available on Hackage: http://hackage.haskell.org/package/zipper . HTH, Stefan