From faul (“rotten”) + Baum (“tree”), from the rotten smell of the bark.
Faulbaum m (genitive Faulbaumes or Faulbaumes, plural Faulbäume)