Alder is native here as well, they are just hard to find in nurseries and get massive for the most part.
I've got three small alders in my small suburban garden. They're native here as well, and I see lots of saplings in the local wood, where it is of course not allowed to take plants from, ahem. Like my fruit trees, they are subjected to pruning to keep them small.
Ceanothus is another N-fixer--I think it's hardy to zone 4. Also laburnum (golden-chain), ulex (gorse), and cytisus (scotch broom)--but check zone hardiness for these. Though cytisus may be illegal in some places, as it's considered an invasive. It's another native here.