What is the maximum number of nodes in a B-tree of order 10 and depth 3, with…

Concept

In a B-tree of order m, each node can have at most m children. Therefore, a fully populated tree has mi nodes at depth i.

For depths 0 through h, the maximum total number of nodes is the geometric sum 1 + m + m2 + … + mh = (mh+1 − 1)/(m − 1).

Application

1. Here m = 10 and h = 3, so the levels are depths 0, 1, 2, and 3.

2. The maximum node counts at these depths are 1, 10, 100, and 1000, respectively.

3. Adding the level counts gives 1 + 10 + 100 + 1000 = 1111.

4. The computed maximum is 1111 nodes.

Cross-check

Using the geometric-series formula gives (104 − 1)/(10 − 1) = 9999/9 = 1111, which matches the level-by-level total.

The computed value 1111 is not among the listed numerical values.