The nice picture in the question does not include the summary nodes nor the min and max fields, both of which are indispensable components of a van Emde Boas tree (vEB tree). A better illustration might be the following picture taken from how to read off the set represented by a van-Emde-Boas tree, which was drawn by Raphael based on a figure in CLRS, where a number in orange is drawn at a min field that marks its presence in the set of integers being represented.
How many nodes are there in the vEB tree implemented like the illustration above?
There are $1 + 5 + 5 \times 3 = 21$ nodes in the illustration above.
For the sake of simplicity, let $w=2^h$ and $u=2^w=2^{2^h}$. A vEB tree over the universe $\{0,1,\cdots, u-1\}$ is of depth $h=\log\log u$.
- There is one node of depth 0, which is the root node.
- There are $2^{2^{h-1}} + 1$ nodes of depth 1.
- Each node of depth 1 has $2^{2^{h-2}} + 1$ child nodes of depth 2.
- ...
- Each node of depth i has $2^{2^{h-i-1}} + 1$ child nodes of depth $i+1$.
- ...
- Each node of depth $h-1$ has $2^{2^{h-h}}+1=3$ child nodes of depth $h$.
In total, the number of all nodes is
$$1 + \sum_{i=1}^{h}\prod_{k=1}^i(2^{2^{h-k}} + 1)=(2^{2^h} - 1)\sum_{i=0}^{h}\frac1{2^{2^i} - 1}\tag{1}$$
which is 1, 4, 21, 358, 92007, 6029862760, 25898063359598159721, $\cdots$ for $h=0,1,2,3,4,5,6,\cdots$ respectively. When $h\ge4$, the number of nodes is about $1.404u$.
Similarly, the number of all summary nodes is, for $h\ge1$,
$$1 + \sum_{i=2}^{h}\prod_{k=1}^{i-1}(2^{2^{h-k}} + 1)=(2^{2^{h}} - 1)\sum_{i=1}^{h}\frac1{2^{2^i} - 1},\tag{2}$$
which is 0, 1, 4, 21, 358, 92007, 6029862760, $\cdots$ for $h = 0,$$1, 2,3,4,5,$$6,\cdots$ respectively.
What is the number of all non-summary nodes? Subtracting (2) from (1), we obtain
$$(2^{2^{h}} - 1)\left.\frac1{2^{2^i} - 1}\right|_{i=0}=2^{2^h}-1=u-1.$$
The formula also hold for $h=0$. So we have obtained the following surprising formula.
$$\text{the number of non-summary nodes in a vEB tree of universe size } u=2^{2^h}\text{ is }u-1.$$
Every node at the same depth use the same amount of space. Nodes at a smaller depth may use much more space than those at a larger depth. For example, for $h=5$, the root node contains a bit-array of size 65536 but a leaf node just contains several words. Since the number of nodes that use bigger space decreases very quickly as their depth becomes smaller, the total space used is $O(u)$.
Exercise. The number of all leaf nodes, which are vEB trees of universe size 2 in a vEB tree of universe size $u=2^{2^h}$ is $u-1$.
