# About balanced and complete binary tree

I found this and I just couldn't verify it. How come it is true?

The maximum number of nodes that a balanced binary tree with depth $d$ is a complete binary tree with $2^d-1$ nodes.

Let say I have the following tree

   1
/ \
2   3


The tree is balanced as well as a complete binary tree. The depth of the tree is 1. So according to the formula the max number of nodes should have been 2^1-1 =1 which is not but 3 in this case.

How come the statement

The maximum number of nodes that a balanced binary tree with depth d is a complete binary tree with 2d−1 nodes

correct then. Can anyone please clarify?

-

Maybe this diagram will be clearer. It shows the full balanced binary trees of depths 1, 2, 3, and 4. The tree of depth 0 has no nodes at all.

The first tree has 1 node. The tree with depth 2 has twice as many (in green and blue) plus a root node (in red), which makes $2\cdot1+1 = 3$.

The tree with depth 3 has twice as many again (in green and in blue) plus a root node (in red), which makes $2\cdot3+1 = 7$.

The tree with depth 4 has twice as many again (in green and in blue) plus a root node (in red), which makes $2\cdot7+1 = 15$.

There are two things to know about this. First, if $M(d)$ is the number of nodes in the full binary tree of depth $d$, then $M(d+1) = 2M(d) + 1$. You can see that from the diagram, since a tree of depth $d+1$ consists of two copies of the tree of depth $d$ (one in green and one in blue) plus a root node (in red). Each tree has the same kind of structure:

The second thing to know is that $M(d) = 2^d-1$ for all $d$. I will show that now.

I claim that the number of nodes in the tree of depth $d$ is always $2^d-1$. Suppose this was wrong, that there were some tree with some other number of nodes. Then among all such trees, there must be one with the smallest possible depth. Let's say that the smallest tree for which the claim fails has depth $m$.

Now evidently $m>1$, because you can see from the diagram that the claim is true for trees of depth 1. But a tree of depth $m>1$ is made of two smaller trees of depth $m-1$ (one in green, and one in blue) plus one root node (in red).

We said that the depth-$m$ tree is the smallest one for which the claim fails. So the claim is true for the smaller trees of depth $m-1$: they have $2^{m-1}-1$ nodes each. Then the depth $m$ tree has $2^{m-1}-1$ green nodes, $2^{m-1}-1$ blue nodes, and one red node, for a total of $\color{green}{2^{m-1} - 1} + \color{blue}{2^{m-1} - 1} + \color{red}{1}$. This adds up to $2\cdot2^{m-1} - 2 + 1 = 2^m - 1$, so the claim is true for our tree of depth $m$ also. This contradicts our assumption that there was a tree for which the claim was false, so our assumption must be wrong, and so there is no such tree and there is no such $m$.

-
You said "You can see that from the diagram, since a tree of depth d+1 consists of two copies of the tree of depth d (one in green and one in blue) plus a root node (in red). Each tree has the same kind of structure:" Can you show it pictorially with a dashed line or something . I am having trouble follwing this premise.. –  Geek Aug 3 '12 at 11:00
I showed it pictorially by putting the two copies of the smaller tree in green and in blue, and the root node in red. –  MJD Aug 3 '12 at 11:52
you mean the second picture in your post ? –  Geek Aug 3 '12 at 11:57
Both pictures in the post. –  MJD Aug 3 '12 at 12:44
Say $M(d)$ is the maximum number of nodes in a tree of depth $d$. This tree has a root node, a left subtree of depth at most $d-1$, and a right subtree of depth at most $d-1$. If you want the tree to have the maximum number of nodes, then the left and right subtrees must individually have the maximum possible number of nodes, namely $M(d-1)$. So we have: $$\begin{eqnarray}M(d) & = & 1 + M(d-1) + M(d-1) \\ & = & 2M(d-1) + 1\end{eqnarray}$$
and clearly $M(0)=0$. The function $M(d) = 2^d-1$ satisfies both those conditions, so that's the answer.