Those street trees are probably the same or closely related to the cherry plums Watto has posted. they are very common street trees and garden trees because thy are hardy and do not need much looking after. The birds eat the plums and spit out the seeds which then start to grow in gardens and along roads, etc. If you look I'm sure there will be some growing in some of the less well kept gardens nearby or along creeks/ drains/ railway and any other untended places. Some have red/purple colored leaves and some types have green leaves.I wasn't aware they were so common like that, there are in fact a lot in the streets of the suburb I live in, they look like the same species that watto recently posted in flower... Can't collect those unfortunately
Do the propagate easily?
I think someone already mentioned that plums are quite easy to strike as cuttings or layering.