War, despite what many would have you believe, is largely about logistics. So let's look at how societies would be affected, because that will greatly affect your supplies, movement, and more.
Like most other answers, I agree that the disappearance of trees would result in a complete collapse of society. The only thing I might say differently is how society collapses.
The first thing I think people may have missed is...
Without trees (and their roots) soil will erode
This will wreak havoc on almost every food source available to humans.
- Fertile soil will begin eroding, meaning domesticated plants won't grow.
- Many types of birds will die out or be severely reduced in numbers by a lack of habitat.
- Many types of animals who hide in forest environments will die, and predators of those animals will attempt to hunt livestock.
- Soil from the mountains will erode onto grass fields, devastating grazing animals in many places.
- Dangerous mudslides will occur burying towns, roads, livestock...
- Dirt will go into rivers and often clog them, killing many types of fish we rely on to eat.
- Harbors will be silted.
- Seashore ecosystems will also be devastated by the large influx of new minerals and components.
Soil erosion based on clear cutting is a likely cause of many civilization collapses in our history (think the Easter Island civilization, possibly the Mayan civilization, and others); how much more so the complete disappearance of trees?
The only source of food that potentially wouldn't be effected would be ocean fishing... but, as has been made clear in other answers, ships won't be able to function without wood for repairs for long.
Effects on Humans and Responses to Responses
At this time I'll take a moment and ask: during the current pandemic when toilet paper was being hoarded, fights broke out over it at the super market... so what would happen if the thing that was scarce was what you cooked with, was what you did your job with, was what kept you from freezing to death in the winter?
In our world, it would be like if oil suddenly disappeared. Yes, we have other sources of energy, but are they enough? There are some movie franchises, methinks, that would argue otherwise.
Growing Food
Obviously, growing food will quickly become a problem based on the above discussion of soil erosion and logic from other answers. I won't duplicate that here.
Processing food
In the medieval period, wheat was ground into flour on an industrial level by water wheels and wind mills. Both of which were usually made of wood. And both of which endure large mechanical stresses on a daily basis. They would break rapidly, meaning that what food stores you might have would soon need to be processed manually, which, while possible, greatly reduces efficiency.
Cooking food
Perhaps more immediately, cooking will become a problem.
At the time that trees disappeared, many people would be relying on wood for heating their food. Much of the time they will have stocked up some amount of firewood, but not an outrageous amount: there's a whole forest right there, why hoard wood? In cities they might have less, as they need to buy the wood instead of chopping it down themselves/with their community.
After going through the few days of firewood people in those areas have stored, what will they do? If peat etc are not currently a part of their heating strategies, then they'll have to burn finished goods for heat. Furniture, tools, abandoned buildings, all start getting thrown into the fire. Civilization is eating itself.
Peat, Coal, etc
Even in places where peat is burned, the huge influx of demand will create shortages. Could those areas scale up production to meet demand? When they can't mine more because they can't use wooden frames for holding up the shaft? When other groups/cities/countries are attacking them to get hold of the fuel sources they do have?
Heating residences
Next, there's heating. Without wood, many northern climes would become largely uninhabitable except by very few. If you can't start a fire, most of your run-of-the-mill peasants are going to be in big trouble.
Responses to these challenges
Once a baron/lord/king realized that trees were gone, they might attempt to march an army over to the nearest coal mining nation. But as I said at the beginning, war is about logistics.
So: how would he transport supplies? Weapons? Armor? Previously he would have used carts and wagons. Now, though, when an axel breaks, you can't just go off the road and chop down a tree to make a new one.
Worse, due to soil erosion, the roads will be in terrible condition. There will be mud, mud, mud, for as far as the eye can see (if he's lucky and this doesn't happen in the winter). Amounts of clean water large enough for an army will be hard to find, leading to all kinds of infections and diseases.
Once he arrives, how will he create siege engines? Dig sapping tunnels? Those were usually built on the spot. As other answers have noted, cities will be largely impregnable.
Maybe he can just go straight to the mines... Perhaps, but don't you think the existing rulers will have taken all the peat/coal behind walls? Ok then, maybe he can just guard the mine while his soldiers mine the materials. Great, how will he transport his ill gotten gains back to his people? Over those bad roads, with too few carts that have been cannibalized endlessly, pulled by draft animals with no grazing, led by men with dysentery.
So he gets home, only to find his people (with the help of his desperate garrison) have ransacked his castle in order to find things to burn. Peasants are now dying in droves, and have found a new leader while he was gone.
And so on.
Conclusion: Effects on Warfare
The effects on warfare would be immediate and drastic: there would be a lot of it, and it would be largely ineffective. Bunches of failed forays into other countries, which quickly devolve into populace control, until, finally, armies as a concept would cease to be viable.
Any civilization that lasted long enough to worry about how heavy an all metal pike is would count itself lucky. It would be a super power in its (limited) area, and organization, supplies, and numbers would easily overcome any bedraggled, starved enemies. Technological and societal advance would slow to a crawl as stone and metal became the only feasible building materials. It would be extremely vulnerable to starvation, bad weather/seasons, and disease.
As far as armaments and tactics go, many other answers, and the question itself, covers many feasible possibilities. But, as a short, speculative list:
- Ranged weapons would be confined to slings.
- Sieges would center around waiting a city out
- Cavalry would become much less effective without wood for saddles and grain for horses
- Metal weapons would become even more expensive due to the difficulty in creating more
- Pitched battles, as a result, would likely have more survivors, and may become largely for display (though that is just pure speculation)