Branching morphogenesis helps increase the efficiency of gas and liquid transport in many animal organs. Studies in several model organisms have highlighted the molecular and cellular complexity behind branching morphogenesis. To understand this complexity, computational models have been developed with the goal of identifying the "major rules" that globally explain the branching patterns. These models also guide further experimental exploration of the biological processes that execute and maintain these rules. In this paper we introduce the tracheal gills of mayfly (Ephemeroptera) larvae as a model system to study the generation of branched respiratory patterns. First, we describe the gills of the mayfly Cloeon dipterum, and quantitatively characterize the geometry of its branching trachea. We next extend this characterization to those of related species to generate the morphospace of branching patterns. Then, we show how an algorithm based on the "space colonization" concept (SCA) can generate this branching morphospace via growth towards a hypothetical attractor molecule (M). SCA differs from other branch-generating algorithms in that the geometry generated depends to a great extent on its perception of the "external" space available for branching, uses few rules and, importantly, can be easily translated into a realistic "biological patterning algorithm". We identified a gene in the C. dipterum genome (Cd-bnl) that is orthologous to the fibroblast growth factor branchless (bnl), which stimulates growth and branching of embryonic trachea in Drosophila. In C. dipterum, this gene is expressed in the gill margins and areas of finer tracheolar branching from thicker trachea. Thus, Cd-bnl may perform the function of M in our model. Finally, we discuss this general mechanism in the context of other branching pattern-generating algorithms.