|
A complete binary tree is defined as a tree where each node has either $2$ or $0$ children. A variety of sources have described the relation between nodes and leaves to be $2n-1$ where $n$ is the number of leaves. I haven't however been able to find a description of how this relation was derived. |
|||||
|
|
Any complete binary tree can be seen as the structure of a single elimination tournament with $n$ teams corresponding to the leaves. Each non-leaf is a game in which the loser goes home and the winner goes up to the next round. There is one final champion, who wins the root game, and so there must be $(n-1)$ non-leaf nodes since every other team loses exactly once. Hence $n + (n-1) = 2n-1$ nodes altogether. |
||||
|
|
A complete binary tree always has $2^m$ leaves for some $m$. Now how many nodes will it have? Well, it will have $1$ root, and $2$ children of the root, and $4$ total children of those children, and so on, up to and including the $2^m$ leaves. So there will be $$ 1 + 2 + 4 + 8 + \cdots + 2^m = \sum_{i = 0}^m 2^i $$ total nodes in a complete binary tree with $2^m$ leaves. Now there is a standard formula that $$ \sum_{i = 0}^m 2^i = 2^{m+1} - 1. $$ If we start by saying that $n = 2^m$ is the number of leaves then $2^{m+1} -1$ nodes is the same as $2\cdot 2^m - 1 = 2n - 1$ nodes, which is the formula requested in the question. |
|||||||
|
|
Well start off with the parent node. If you only have one node, that's one leaf, and $2(1) - 1 = 1$. This equation implies that every time you add another leaf, then the total number of nodes will increase by 2. Now adding two children means taking away one leaf (the parent used to be a leaf) and adding adding two new leaves, which gives a total of one new leaf. You are adding two nodes from one extra leaf, so it turns out this equation works out. |
||||
|
|
|
Start out with a list of $n$ leaf nodes: we will consider this as a list of nodes which we have to give parents, to construct a complete binary tree. Take any two nodes $a,b$ from the list, and give them a common parent $p$. (We must take them in twos, to satisfy the completeness property of the tree.) Now those two nodes have parents, but the new parent node $p$ does not; so we remove $a$ and $b$ from the list and add $p$ in. This reduces the size of the list by 1, no matter how we choose the nodes to give parents to. We may then repeat this, giving a parent to two other nodes (where one of them is possibly the node $p$ which we just inserted). We will have finished constructing the tree only when there is one node left with no parent: the root node of the tree. Doing this requires $n-1$ stages of creating new parent nodes. Thus, to build the tree from $n$ leaves, we needed to add $n-1$ new nodes. |
|||
|
|
|
Try deleting a leaf node... you need to delete the edge supporting it, and then merge the two edges adjacent to that edge (thereby deleting a second node) in order to have a complete binary tree again. So the number of nodes and edges are both of the form $2n + k$. The trivial tree has $1$ leaf and no edges and one node... so the number of nodes must always be $2n-1$, and the number of edges must always be $2n-2$. |
|||
|
|
|
Adding two edges to a leave cancels one leave and adds two new leaves while adding two nodes hence the number of nodes minus twice the number of leaves is an invariant. Since every binary tree can be built by a finite number of such steps and, for the tree with one vertex and no edges, this invariant is $1-2\cdot1=-1$, for every binary tree the number of nodes plus one is twice the number of leaves. This, or Euler characteristic. |
|||
|
|
