How to achieve full number of words in a Bag-of-Features model based on Hierarchical K-Means?
Unfortunately, I think what causes the problems is most probably the training set of images you're using to construct the tree. (or, more in general, the database you're working on). Without a way to inspect the concrete images, I can only give a few vague guesses.

First, I would diagnose where it goes wrong, by simply inspecting the tree and looking at the first branches which become severely underpopulated and consequently don't branch any more in the lower levels. I would look at those features and... think. But, since I can't actually do that since I don't have your dataset, let me try further.

If you're afraid that it's the K-means that is going wrong, not because the features aren't (more-or-less) uniformly distributed over the feature space, but simply because of the way that algorithm works, before implementing a fancier algorithm, you might first try running K-means several times for each branching and picking the best result (e.g. the one that divides the feature space in most equal parts). This will probably be too slow for the final implementation, but it could be a fast, minimum-effort way do diagnose the problem.

I would say, in order for HKM to work, your initial number of features should be several orders of magnitude greater than the expected number of clusters. So, if that's not the case, you know you're doing something wrong. I don't know how many is enough, but I would say minimum $100$ times, but better at least $1000$ times more features than expected clusters. This might be caused by two (related) issues:


Maybe your training set is just too small, or maybe it is a bad representation of the database, containing images that are too similar? Try increasing the size of the training set, and maybe (just for testing purposes), cherry pick the training set by selecting very different, representative images. 
Maybe your feature detector performs badly on the image set you're using. For some images, some detectors just do not detect enough features. Problematic images usually contain large single-colored areas (e.g. white wall, blue sky). Try combining several feature detectors. (e.g. in my thesis I was working with DoG and MSER features). You can always do that, since you can finally describe all the features from several detectors with the same descriptor.




Unfortunately, there's no more ideas I can think of based on so little information. You might simply have an implementation error sometimes. I know it's not easy to here, and it's not a most helpful diagnosis, but as somebody who actually implemented such a CBIR system, I have to tell you, I never had any problem in constructing a vocabulary tree of expected size.

If you give any more info, or updates, or whatever, I can try and think of other ways this might have gone wrong. Until then, I hope this helps.