There is a Sherlock Holmes story called "the Copper Beeches", referring to the color of the trees and not what they are made of. A tree that I often saw at the Demuth Tobacco Shop at 114-116 East King Street, Lancaster, Pennsylvania was called a copper beech.
Fagus sylvatica purpurea is a variety called the copper beech or purple beech.
leaves purple, in many selections turning deep spinach green by mid-summer.
Here is a link to a photo of a copper beech in spring:
Then there is the Summer Red Maple:
An outstanding shade tree with burgundy red new foliage that matures to dark purplish green; in autumn, older leaves turn yellow while younger ones turn orange or purple; a dense broad tree that provides welcome summer shade.
For red color from spring through fall, plant a "Bloodgood" Japanese maple (Acer palmatum "Bloodgood"). This 20-foot-tall tree thrives in partially to fully shaded sites in U.S. Department of Agriculture plant hardiness zones 6 to 8. Its palmate leaves emerge red in spring and deepen over the growing season. Another 20-foot tree, the tricolor dogwood (Cornus florida "Welchii") has red, pink and green foliage. This deciduous tree is hardy in USDA zones 5 to 8 and thrives in shady sites with acidic, moist soil. The tricolor dogwood blooms with pink-white spring flowers, followed by red fruits.
In spring, the "Royal Purple" smoke tree (Cotinus coggygria "Royal Purple") buds with red-purple leaves that keep their color through the growing season. In summer, red and purple blossoms add even more color. This 25-foot-tall tree is hardy in USDA zones 5 to 8, where it grows best in sunny exposures with well-draining soil. The "Newport" purple leaf plum (Prunus cerasifera "Newport") also has red-purple foliage. Reaching heights of 25 feet, this colorful tree also blooms with showy pink flowers in late winter, before the red-purple new growth appears in spring. Hardy in USDA zones 5 to 9, this plum tree grows well in moist soil.
For red spring leaves with a hint of copper, plant a bronze dracaena (Cordyline australis "Atropurpurea"). This evergreen has red-copper foliage that's offset by its fragrant, white spring flowers. Hardy in USDA zones 10 and 11, the bronze dracaena grows to 35 feet tall and tolerates drought, dry soil and alkaline pH. Also reaching heights of 35 feet, the "Rubylace" locust (Gleditsia triacanthos var. inermis "Rubylace") has red, purple and green leaves that turn yellow in fall. This spreading tree grows well in a variety of soil types, sun exposures and pH levels, but it doesn't tolerate salt spray. "Rubylace" is hardy in USDA zones 3 to 7.
The "Tricolor" European beech (Fagus sylvatica "Tricolor") has red, green and white leaves that darken to bronze in autumn. This deciduous tree grows to 45 feet tall and has a conical shape. It's hardy in USDA zones 5 to 7 and grows best in moist, acidic soil. Fill a large space in the landscape with a Chinese sweetgum (Liquidambar formosana). Reaching heights of 65 feet, this spreading tree has red-purple new growth that darkens to green, then turns red and yellow in fall. The Chinese sweetgum is hardy in USDA zones 7 to 9 and grows best in moist, acidic soil.
So some Earth trees do have red leaves in seasons other than fall. To create a world where every species of tree everywhere has red leaves in every season you would have to replace chlorophyll with some other chemical for photosynthyesis; but if characters only visit one region on that world there might be only a few closely related species of trees there which all have red or reddish leaves in spring and/or summer, even if most trees in most regions of the planet have green leaves in spring or soummer.
..and some are even capable of growing on rocks..."
suggests that region of the planet might be rockier and have poorer soil than most regions of it.
As for bark, apparently a lot of tree species have red or reddish bark.
One of the most famous such trees is the coast redwood, Sequoia sempervirens:
The bark can be very thick, up to 1-foot (30 cm), and quite soft and fibrous, with a bright red-brown color when freshly exposed (hence the name redwood), weathering darker.
And some trees have much redder bark - here is a link to a photo of a much redder tree trunk: