I am reading about B-Tree through CLRS. One of the exercise problem is to express maximum number of keys in a BTree of height $h$ and minimum degree $t$.

Properties of BTree of $t$:

  • $t\ge 2$
  • Min. no of keys in a node is $t-1$ and max. number of keys in a node is $2t-1$
  • Max number of children a node can have is $2t$

To solve it the formula I came up with is $$\sum_0^h (2t)^h(2t-1) $$

Does it have any convergence?

  • $\begingroup$ convergence doesn't seem to be the precise term. $\endgroup$
    – greybeard
    Feb 2, 2020 at 7:52
  • $\begingroup$ @greybeard that was the closes term that I could think of. Maybe reduction?? $\endgroup$
    – Sab
    Feb 2, 2020 at 7:59

1 Answer 1


Found it (using geometric serie for the sum)

$$\sum_{i=0}^h (2t)^i(2t-1) = (2t-1) \sum_{i=0}^h (2t)^i = (2t-1) \frac{(2t^{h+1}-1)}{(2t-1)} = (2t)^{h+1}-1 $$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.