Why do some trees have leaves that are not green?

Ever wondered why some tree leaves are red, blue or even dark purple, and not green? How does that work?

Most trees have green leaves, and that is because of the presence of photo-active pigments chlorophyll, which absorbs most of the red and blue parts of the light spectrum, while reflecting back the green parts, which is what we see. Chlorophyll is used by the trees' leaves in the biochemical process of photosynthesis, which is how plants convert sunshine into energy in order to grow.

Some trees, though - ornamental ones like plum trees, Japanese maples and purple beeches, but also several wild species in the rainforests of the world - have red, purple, blue, even almost black, leaves. These leaves still have plenty of chlorophyll for their photosynthesis needs, but they have even more of other pigments like carotenoids (red/orange/yellow), anthocyanins (purple/red), fucoxanthins (brown), phycobilins (blue), etc, which reflect more of other colours than the green. Thus, the green colour is effectively masked by the relative abundance of the other pigments, and the leaves appear to us as purple, red, etc. These pigments are also known as "accessory pigments" because they are not able to use sunlight energy directly in the photosynthesis process, but have to first pass their absorbed energy to chlorophyll.
So, why would a tree choose to go down this apparently inefficient evolutionary route? This is not well understood, but various hypotheses have been put forward, from the idea that the accessory pigments help a plant to reabsorb nitrogen, to the idea that antioxidants in the pigments help protect the leaves from sun damage or aid in the tree's preparation for the growth shut-down of winter, to the possibility that they are just trying to confuse and deter insects and other herbivores that might otherwise want to eat their leaves, or to protect them from fungal infections.
Or they might just be free spirits and non-conformists...