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?
Best Answer
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$.