Are you guys referring to growing these trees/plants in a permie setup, or using the wood in hugelkultur beds, or both?
We have several natives in AZ that known nitrogen fixers...many of those are legumes. Several varieties of acacia, cercidium (palo verdes), calliandra, ironwood, lupine, senna, and just about any mesquite of course. The only ones I might personally consider in a completely fabricated permaculture environ might be Chilean mesquite (which is not native), or a Honey mesquite. The beans can be used for flour, and the branches can be used for smoking meats.
