Trees sustain livelihoods and mitigate climate change, but a predominance of trees outside forests and limited resources make it difficult for many developing countries to conduct frequent nation-wide inventories. Here, we propose a rapid and accurate approach to map the carbon stock of each individual tree and shrub at the national scale of Rwanda using aerial imagery and deep learning. We show that 72% of the mapped trees are located in farmlands and savannas, and 15% in plantations. These non-forest trees account for 41% of the national carbon stocks. Natural forests cover 5% of the country and 11% of the total tree count, but comprise 59% of the national carbon stocks. The mapping of all trees facilitates any landscape stratification and is urgently needed for effective planning and monitoring of landscape restoration activities as well as for optimization of carbon sequestration, biodiversity and economic benefits of trees.