The universe size $ u$ in vEB trees is square rooted at each level until $ u = 2$ . So, unlike search trees, the branching factor is different at each level.

The height of the tree is $ h = \lg \lg(u)$ and $ u$ is an even power of 2, $ u = 2^{2^k}$ . I tried to calculate the count using the sum:

$ $ \sum_{i=1}^{h-1} 2^i\,2^{i + 1}$ $

But it doesn’t work. Any idea on how to do the math?