In Finland, the tree of choice for smoking is alder (leppä), but this is difficult to find in Australia and close to impossible to import due to biosecurity restrictions. What's my best substitute? I'm particularly interested in smoking fish (salmon, trout).
Peach and Apple wood are readily available, and I use them regularly for fish.
You may find that since the wood is in fact considered treated, you may find it is in fact available...
Most fruit producing trees produce a nice smoke for fish.