3
$\begingroup$

In one of the lectures I went to, my professor stated that in order to determine the size of a search tree, we use the following formula: $$\frac{b^{d+1}-1}{b-1},$$ whee $b$ is the branching factor and $d$ is the depth of the tree in question. I would like to understand why we divide by $b-1$. I would have thought that the correct solution is $b^{d+1}-1$.

$\endgroup$
1
  • $\begingroup$ You're probably tricked by usually nice case of $b=2$, where you have $2-1 = 1$. $\endgroup$
    – user5386
    Dec 14 '16 at 20:25
5
$\begingroup$

There are $b^i$ nodes at depth $i$, and so the total number of nodes is $$ 1 + b + b^2 + \cdots + b^d = \frac{b^{d+1}-1}{b-1}, $$ using the formula for the sum of a geometric progression.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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