His music isn't really in any category. He makes jazz references in some of the titles, and he recorded for Prestige, largely a jazz label, but his music is not improvised.
I never got to see him on the streets of New York, but I do remember seeing him on the Tonight Show when his first Columbia album was released.
I played him on the air several times, and always got calls, so I guess his music was compatible with jazz.