2
$\begingroup$

I'm reviewing some of the theorems that make up the Full binary tree theorem and want to make sure my proof for how the number of internal nodes $I$ is related to the number of total nodes $N$ is correct.

I realize you could relate the number of internal nodes to the number of leaves and them simply add, and go from there but I'm trying not to use that proof in this example.

I'm using induction and I believe my proof valid but something about it seems so simple (and a bit wordy) I'm not sure if I'm missing something. Also if there are any other proofs someone would like to dish out that would be great. I realize you could do this purely with numbers and less "english" if trying to prove this on a perfect binary tree (much tighter restrictions on the tree), however the most concise way I can think of proving this for a full binary tree is rather wordy, and below.

The total number of nodes $N$ in a tree with $I$ internal nodes is $2I + 1$

Base case

A tree with $0$ internal nodes $I$ has $2(0) + 1 = 1$ total nodes.

Assumption

Let's assume that any full binary tree with $I$ internal nodes has $2I+1$ total nodes $N$.

Inductive step

Given a tree $T$ with $I+1$ internal nodes, take one of it's internal nodes whose children are both leaves and remove it's children. $T$ now has one less internal node or $I$ internal nodes meaning it has $2I+1$ total nodes. If we add the children back to our selected node, the number of internal nodes increases by $1 \text{ from } I \Rightarrow I+1$ and our total number of nodes $N$ increases by $2 \text{ from } 2I+1 \Rightarrow 2I+3$ which is the same as $2(I+1) + 1 \quad \blacksquare$.

$\endgroup$
2
$\begingroup$

You went slightly astray with the last sentence: you lost track of the number of internal nodes. If we add the children back in, the number of internal nodes increases by $1$ from $I$ to $I+1$, not from $I+1$ to $I+2$. You also need to show that there actually is an internal node whose children are both leaves. If you’ve already defined the height (or depth, depending on your terminology) of a node, you can pick a leaf $v$ whose height is maximal: its sister must also be a leaf. You can also add a little connective tissue to the induction step, something like this:

Suppose that the result is true for all full binary trees with $I$ internal nodes, and let $T$ be a full binary tree with $I+1$ internal nodes and $N$ nodes altogether. $T$ has at least one internal node, so it must have a leaf; let $v$ be a leaf of maximal height, so that its sister is necessarily also a leaf. Remove $v$ and its sister, and let $T'$ be the resulting tree; the parent of $v$, which was an internal node of $T$, is a leaf of $T'$, and the status of the other nodes of $T'$ is unchanged, so $T'$ has $I$ internal nodes. It is also a full binary tree, so by the induction hypothesis $T'$ has $2I+1$ nodes altogether. Clearly $N=(2I+1)+2=2(I+1)+1$, as desired.

$\endgroup$
  • $\begingroup$ If I add the case where $I = 1$ to the base cases, is that enough to prove that some internal node with two leaf children does exist, since at least two leaves exist (and obviously they must be parented by one internal node)? $\endgroup$ – Dominic Farolino Jul 1 '16 at 23:34
  • $\begingroup$ @DomFarolino: No, because there can be leaves whose sisters are internal. $\endgroup$ – Brian M. Scott Jul 1 '16 at 23:41
  • $\begingroup$ Ok, so that is why I need to specify to choose two leaves that are at the maximum depth of the tree then. Thanks $\endgroup$ – Dominic Farolino Jul 1 '16 at 23:49
  • $\begingroup$ @DomFarolino: That’s right. You’re welcome. $\endgroup$ – Brian M. Scott Jul 1 '16 at 23:52
  • $\begingroup$ Quick question, is the first proof on this page incorrect for your previous reasons? While having the base case $I = 1$ proves some internal node with two leaves does exist, there is no picking leaves based off of height/depth $\endgroup$ – Dominic Farolino Jul 2 '16 at 1:29
1
$\begingroup$

To carry out the inductive step, you need an internal node with two leaves. You might have to prove that such a node exists for $I\geq1$ in a full binary tree. You can avoid that by choosing any internal node except the root and removing the full subtree rooted at it, thereby adding a leaf node to the original tree in its place.

This, however, needs a full tree with a non-root internal node in the inductive step, that is, $I\geq2$, so consideration of $I=1$ must be added as base case.

$\endgroup$
  • $\begingroup$ Since I need to add $I = 1$ as a base case to show that there exists some internal node (not the root) that has a whole subtree rooted at it, does this also imply that there obviously must exist some internal node which parents two leaves? It seems a tad less explicit this way but they seem to mean the same thing to no? $\endgroup$ – Dominic Farolino Jul 1 '16 at 23:20
  • $\begingroup$ Whenever you choose something, you have to prove the existence first. Existence of a proper subtree seems less of a requirement than existence of a full 3-node subtree. But, thinking about it, my use of subtrees relies on the fact that trees are connected acyclic graphs, otherwise you'd have to cut more than one edge. And that subtrees of full trees are full as well. For a full 3-node subtree that's more obvious than for an arbitrary-size subtree. $\endgroup$ – ccorn Jul 1 '16 at 23:37
  • $\begingroup$ Ok, makes sense that we need to prove what we decide to choose. It sounds like at the end of your comment you're saying that its easier to prove a full 3-node subtree exists in a full tree with $I \geq 1$ internal nodes than it is to prove a full arbitrary-size subtree exists? $\endgroup$ – Dominic Farolino Jul 1 '16 at 23:56
  • $\begingroup$ If part of your definition of a full binary (sub)tree is that every non-root node has degree either 1 or 3, then it is easy to deduce that the subtree is full. This illustrates the need to avoid "easy to see" shortcuts and use definitions instead. $\endgroup$ – ccorn Jul 2 '16 at 0:06
0
$\begingroup$

Let $N$ be the total nodes in tree $T$, of which $I$ nodes are internal. Since, the root vertex of a binary tree is of degree $2$, $(N-I)$ leaves are of degree $1$ and rest $(I-1)$ vertices of degree $3$, thus by Handshaking theorem, one gets

$\sum_{r=0}^{n}deg(v_r)=2(no. of edges)$

$\implies 2+(N-I)+3(I-1)=2(N-1)$

$\implies N=2I+1$

$\endgroup$
  • $\begingroup$ The explanation applies only to full binary trees with more than one node, but apart from that, it's a nice proof, like that one. Here, we focus on the OP's induction approach however, otherwise Brian's alternative proof would apply as well.. $\endgroup$ – ccorn Jul 3 '16 at 12:11
  • $\begingroup$ @ccorn...yes I agree $\endgroup$ – Mathlover Jul 3 '16 at 14:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.