How did flowers evolve on both trees and plants?

Flowers could have evolved more than once. Comparing the genomes of plants has inclined many to this opinion. If they have multiple origins then more than one of the current theories may be correct. The one thing they have in common is that the smaller plants or understory trees where the first to develop a symbiotic relationship with insects rather than just rely on wind. Tall canopy trees like the Progymnosperm Archaeopteris or the true conifers relied on wind more easily since with height the pollen could travel farther.

Paleoherb or the 'sneaky herb' theory suggests smaller herbs or even grasses started it all. The plants began with separate single sex (dioecious) plants. These have the oldest known fossil as evidence. A 120 million year old member of the pepper family, a Piperaceae. The small plants were weedy, fast growing colonizers looking for disturbed soil. They came to this open habitat then had to find each other over longer distances to mate. Large open habitats drove the shift to grow floral structures to attracts insects as aids in pollination. So flowers came as an adaptation to large open spaces to ensure sexual reproduction at long distances between single sexed flowers.

However another of the theories, supported by some molecular studies, is the Woody Magnoliid or the Euanthial theory that says small trees or woody shrubs (magnolia-like plants) with cone-like flowers are the common ancestors. This has the insect pollination syndrome as the driving force rather than habitat.

Here it is suggested the exposed female gamete of the conifer’s cone was gradually enfolded by an increasingly protective structure. The structure became the plant's ovary eventually.
The female gamete is exposed once the cone’s scales open for pollination and is good food for foraging insects. If the cone developed a cupped shape around the female gametophyte there was more protection but pollen was not blocked from entering with the wind. The more the insects became involved in the pollen delivery process the more enclosed the female gamete could become. Insects bearing the pollen could crawl into where the female gamete was when wind failed to push the male gamete in.

These were shrubby, short, under story trees with broad leaves to catch light penetrating the canopy of archaeopteris and true conifers.

True flowering trees evolved from the first flowering plants. Just as Insect diversity increased dramatically following the origin of the flowering plants so the plants themselves adapted to every possible niche.