22
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ !Farhad Yusufali: Please see the comments below my answer, and decide whether you should accept a different one. $\endgroup$
    – Carl Mummert
    Aug 8, 2012 at 12:01
  • $\begingroup$ See also here. $\endgroup$
    – Raphael
    Aug 8, 2012 at 19:38
  • $\begingroup$ The page here has this question for strictly binary trees, but it would work easily for complete binary tree as well: stackoverflow.com/questions/4279963/binary-tree-data-structures $\endgroup$
    – Anupam Jain
    Jul 19, 2016 at 10:37
  • 1
    $\begingroup$ Isn't the correct terminology "full" not "complete"? $\endgroup$
    – TorsionSquid
    May 18, 2018 at 23:16

8 Answers 8

Reset to default
29
$\begingroup$

Any full 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.

$\endgroup$
4
  • 1
    $\begingroup$ Very intuitive example, +1! $\endgroup$
    – Georgey
    Dec 15, 2013 at 22:21
  • $\begingroup$ In general for complete n-ary tree (one in which every node has 0 or n children), if $x$ is the number of internal nodes, the number of leaves in it is $x(n-1)+1$ and thus total number of nodes is $xn+1$ $\endgroup$
    – Maha
    Jan 26, 2015 at 20:30
  • 1
    $\begingroup$ I think you are talking about full binary tree because a complete binary tree can have one leaf node. $\endgroup$
    – CodeYogi
    Aug 22, 2016 at 3:01
  • $\begingroup$ We are using the definition of "complete binary tree" given in the OP above (every node has either 0 or 2 children), in which case just one leaf node means that's the only node in the tree (trivial tournament with only one team and no games). If "full" is the more common term for that, well, a rose by any other name ... $\endgroup$
    – Ned
    Aug 23, 2016 at 20:27
13
$\begingroup$

A perfect (complete and full) 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 perfect 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.

$\endgroup$
6
  • 2
    $\begingroup$ It's not true that a complete binary tree has $2^m$ nodes. For instance, consider the case where the root has a left and right child, the left child of the root has no children, and the right child of the root has a left and right child neither of which has any children. This tree is complete by the poster's definition - each node has either 2 children or none - but it has only three leaf nodes. $\endgroup$
    – Steven Stadnicki
    Aug 8, 2012 at 3:27
  • $\begingroup$ Thanks! (Of course you mean leaves rather than nodes.) I didn't actually see that bolded sentence below the question title before, and wrote this on the assumption that "complete" meant, well, complete. Except that when I look at the "binary tree" article on Wikipedia I now see that this term has several meanings in addition to the one the OP may have meant. In any case, my answer was only intended to cover a specific type of tree. I think Ned's answer is quite good for the more general case. $\endgroup$
    – Carl Mummert
    Aug 8, 2012 at 12:00
  • $\begingroup$ Very nicely proved! $\endgroup$
    – Vikram
    Sep 25, 2014 at 1:36
  • $\begingroup$ @CarlMummert (sorry for not putting space there, but StackOverflow mentions works that way I guess) so it doesnt matter which definition for Complete Tree is followed, its always $2n-1$ total number of nodes for $n$ leaves? $\endgroup$
    – Maha
    Jan 27, 2015 at 21:58
  • $\begingroup$ @awellwisher: yes, I believe so. Also, spaces in mentions work fine, as long as the first name is at least 3 letters long. $\endgroup$
    – Carl Mummert
    Jan 28, 2015 at 1:33
7
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ This is an elegant proof. It can be written beautifully using structural induction on the full binary tree. $\endgroup$
    – NotNotLogic
    Jan 26, 2020 at 23:18
2
$\begingroup$

A graph follows a basic property

$$\text{Sum of degrees of all nodes }= 2 \times\text{number of edges}$$

Now since it is complete binary tree it follows:

  1. Leaves are the only nodes with degree $1$; let there be $n$ of them
  2. Root is the only node with degree $2$, there is $1$ root
  3. All internal nodes have degree $3$; let there be $x$ of them

Since tree is also a graph so using the basic property you get

$$n\times 1 + 1\times2 + x\times3 = 2 \times\text{number of edges}$$

To compute the number of edges:

Consider every node except root node, it has exactly one parent edge and every edge is some parent edge. So total number of edges is the number of parent edges which is equal to the number of nodes that have a parent i.e. $n+x$ (root node has no parent)

Hence the equation becomes $$n + 2 + 3x = 2\times(n+x)$$ Whence \begin{align}x = n-2\\ \text{Total number of nodes} &= n + 1 + x &+1\text{ is for root node}\\ &= n + 1 + n-2 = 2n-1\end{align}

$\endgroup$
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

this applies for both complete and strictly binary tree

start with 1 node tree. in which

number of leaves = number of nodes

incase of strictly binary tree - to add one more leaf to the tree we have to add two nodes to the tree, and for one more we have to add two nodes more nodes to the tree and so on.

SO for n leaves the number of nodes will be 2*n -1

in the same way you can extend it for complete binary too.

$\endgroup$