Is it correct to make queries to DB in preprocess functions?
No, it's not incorrect to query the database in a preprocess function. If the information is required to render the page, putting a query in a preprocess function is an acceptable choice. Plus, in this particular case taxonomy_get_tree() caches results, so there is very little cost associated with repeated fetches.

Regarding Views, yes there is some overhead associated with it, but it employs a sophisticated caching strategy, and is ultimately just so powerful and useful that most sites use it. You could probably solve this current problem with no custom code by using a Viewfield.

These questions provide a lot of interesting background on Drupal performance.