# What is the size of the Perfect binary tree with n nodes in last level

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

• 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$. Aug 6, 2013 at 11:27

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

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.
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).
• 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)? Apr 13, 2021 at 16:23
• @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). Aug 1, 2021 at 9:11
• 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}$. Aug 1, 2021 at 9:12