combinatoricstrees
I am confused with this statement
The maximum number of nodes in a binary tree of depth $k$ is $2^k-1$, $k \geq1$.
How come this is true. Lets say I have the following tree
1
/ \
2 3
Here the depth of the tree is 1. So according to the formula, it will be $2^1-1 = 1$. But we have $3$ nodes here. I am really confused with this depth thing.
Any clarifications?
I can think of no definitions of binary tree and distinct that would produce six distinct binary trees.
There are $14$ plane binary trees, i.e., rooted binary trees in which left and right offspring are distinguished. If left and right offspring are not distinguished, there are only three rooted binary trees:
* * *
| | / \
* * * *
/ \ | |
* * * *
|
*
If you consider unrooted trees, the last two of these are the same: there are only two unrooted binary trees.
If you consider labelled trees, the numbers go up considerably: unrooted the chain graph with four vertices already can be labelled in $12$ ways, so there’s no way to get just six.
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$.
Best Answer
It should be $2^{k+1}-1$. The proof is as follows: In a full binary tree, you have 1 root, 2 sons of that root, 4 grandsons, 8 grand-grandsons and so on. So the total number of nodes is the sum of the geometric series:
$$1+2+4+8+\dots +2^{k} = \frac{2^{k+1}-1}{2-1}=2^{k+1}-1$$
where $k$ is the depth (i.e. for $k=0$ we have 1 node).