2
$\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$
1
  • 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
4
$\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$
4
  • $\begingroup$ Yes, each level has one more node than the entire tree above it.. Does it mean that the amount of nodes in the last level of a binary tree linearly dependent on the total amount of nodes in the tree(in case the binary tree is balanced)? $\endgroup$
    – some1 here
    Apr 13 at 16:23
  • $\begingroup$ Can this work for any arity tree? Say I have a 3-arity tree where every interior node has 3 children. Would there be 3^(k+1)-1 nodes? $\endgroup$
    – Breedly
    Jul 31 at 21:35
  • 1
    $\begingroup$ @Breedly, let's repeat the argument. Number of nodes in Level 0: $N_0=1$. Level 1: $N_1=3$.... Level i: $N_i=3^i$ nodes. Total number of nodes up to depth $k$: $N_0+N_1+...+N_k$. This sum gives $\frac{1}{2}(3^{n+1}-1)$ (try in wolfram alpha for instance). $\endgroup$
    – Ran G.
    Aug 1 at 9:11
  • 1
    $\begingroup$ In general, for $q$-ary trees, the sum of the geometric series is $1+q+q^2+\cdots+q^k = \frac{q^{n+1}-1}{q-1}$. $\endgroup$
    – Ran G.
    Aug 1 at 9:12

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.