Newton-Okounkov bodies sprouting on the valuative tree