We describe a methodology to accurately compute halo mass functions, progenitor mass functions, merger rates and merger trees in non-cold dark matter universes using a self-consistent treatment of the generalized extended Press-Schechter formalism. Our approach permits rapid exploration of the subhalo population of galactic halos in dark matter models with a variety of different particle properties or universes with rolling, truncated, or more complicated power spectra. We make detailed comparisons of analytically derived mass functions and merger histories with recent warm dark matter cosmological N-body simulations, and find excellent agreement. We show that, once the accretion of smoothly distributed matter is accounted for, coarse-grained statistics such as the mass accretion history of halos can be almost indistinguishable between cold and warm dark matter cases. However, the halo mass function and progenitor mass functions differ significantly, with the warm dark matter cases being strongly suppressed below the free-streaming scale of the dark matter. We demonstrate the importance of using the correct solution for the excursion set barrier first-crossing distribution in warm dark matter - if the solution for a flat barrier is used instead the truncation of the halo mass function is much slower, leading to an overestimate of the number of low mass halos.