0
$\begingroup$

I want to know how to calculate total number of nodes in a perfect balanced binary tree with $n$ nodes in the last level. I know the answer is $2\cdot 2^{\log n} - 1$. Just curious how this can be calculated

$\endgroup$
  • 2
    $\begingroup$ Have you tried to draw such a tree? Try drawing all such trees of depth up to 5. Is there a relation between the number of internal nodes and the number of leaves? The leaves are the nodes on the lowest level, the internal nodes are all the rest. Just count them and see how it looks. You will find out $\sum_{i=0}^{n-1}2^i$ vs. $2^n$. $\endgroup$ – Pål GD Aug 6 '13 at 11:27
2
$\begingroup$

A perfect (binary) tree of depth $k$ has exactly $2^{k+1}−1$ nodes.

There are probably several ways to prove it. A simple way is by induction. Each level has twice as many nodes as the previous level (since each node has exactly 2 children in a binary tree). The base level - the root - has 1 nodes. Note that the root is depth 0, not 1.

Let's denote the number of nodes in level $i$ by $N_i$. We know,

$N_0 =1$
$N_i = 2N_{i-1} = 2^{i}$

The total amount of nodes (of tree of depth $k$) is $S_k \equiv N_1 + N_2 + \cdots + N_k$, that is,

$$ S_k = 1 + 2 + 4 + 8 + \ldots +2^{k}.$$ This is a geometric series, whose sum is $S_k = 2^{k+1}-1$.

Now for your question:
We are given a perfect (binary) tree with $n$ nodes at the last level, how many nodes does it have overall?
We are given that at the last level (call it level $k$) we have $N_k=2^k=n$ nodes. Then $k=\log_2 n$ and we get that $S_k=2^{k+1}-1=2n-1$; Yes, each level has one more node than the entire tree above it.

A related question:
we are given a perfect (binary) tree with $n$ nodes, what is its depth?
Now we are given that the total number of nodes is $S_k = 2^{k+1}-1 = n$, thus $k=\log_2 (n+1)-1$ (again, the root is considered depth 0 here).

$\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.