Could earth run out of O2?
No, that will not happen. There is just too much oxygen in the atmosphere.

Over 20% of our atmosphere is oxygen. 
Only about 0.04 % of our atmosphere is CO2, so too much CO2 would kill us much sooner than the lack of oxygen. 

If you reduced the oxygen concentration in the atmosphere from 20.8% to 19.8%, you wouldn't even feel the difference. If you reduced it to 15 %, you would still survive it. You could even survive 10 % for short time periods.

However, let's see what would happen if you added CO2 as a replacement for the oxygen you removed: at 1%, you would feel extreme dizziness. At 5% you would lose consciousness and die.

But the real danger in CO2 lies elsewhere. Even an increase from our current 0.040 % to 0.045 % could cause a lot of damage to the climate, and an increase above 0.055 % could be disastrous. Unless you are locked in a small room, the reason why the increase of CO2 and decrease of oxygen will be dangerous won't be because you wouldn't be able to breathe. Changes significantly smaller than those required to make breathing difficult, would be enough to wreck the ecosystem, cause drought, desertification, starvation, and economic collapse.

Also note, that trees are very important for the water cycle, as a habitat for many species, and for preventing soil erosion, but they play an insignificant role in producing oxygen. Most of our oxygen is produced by algae.