0
$\begingroup$

This is some problem from an old MIT Discrete Maths course:

We define a Splitting Binary Tree, or SBTree for short, as either the lone vertex, or a tree with the following properties:

  1. exactly one node of degree 2 (called the root).
  2. every other node is of degree 3 or 1 (called internal nodes and leaves, respectively).

Prove that two SBTrees with the same number of leaves must also have the same total number of nodes. Hint: As a conjecture, guess an expression for the total number of nodes in terms of the number of leaves $N(l)$. Then use induction to prove that it holds for all trees with the same $l$

So they are talking about a full binary tree. I use this in my proof, as it seems the more common term.

Any feedback for the correctness and style of the proof would be appreciated!


Conjecture: A full binary tree with $l$ leafs has $n = 2l - 1$ nodes in total. This conjecure is based on the observation that the root node splits into two children. Or, from the other direction, two child nodes are folded into one parent node.

Proof: In a given full binary tree $T(V, E)$ all vertices have either $0$ or $2$ children, satisfying the property that there exists a root with degree $2$ and all other vertices have either degree $1$ for leafs or degree $3$ for non-root internal vertices. Alternatively, $T$ only consists of a single vertex.

Let $P(n)$ be the proposition that $T$ has $2l - 1 = n$ nodes, where $l$ is the number of leafs in $T$ and $n = |V|$. We proceed by induction on $n$.

Base Case, $P(1)$

$T$ only consists of a single vertex, which can be considered the only leaf in $T$. Since $n = 1$ and $l = 1$, we find that $2 * 1 - 1 = 1$, so $P(1)$ holds.

Inductive step, $P(n+1)$

We need to show that for a full binary tree $T$ with $n+1$ vertices, we find that $2l - 1 = n + 1$, where $l$ is the number of leafs in $T$.

The root of $T$ has exactly $2$ children, otherwise $P(1)$ would apply. So $T$ consists of one root and two subtrees, call them $U(E_U, V_U)$, $W(V_W, E_W)$.

The sum of the vertices in $T$ is equal to the sum of the vertices in its two subtrees plus $1$ for the root of $T$:

$$n + 1 = |V_U| + |V_W| + 1\tag{1}$$

Let the number of leafs in $U$ be $u$ and the number of leafs in $W$ be $w$. As both subtrees $U$ and $V$ have $< n+1$ vertices, we can assume $P(n)$ for them, that is:

$$|V_U| = 2u - 1$$ $$|V_W| = 2w - 1$$

Let the number of leafs in $T$ be $l$, which is the sum of all leafs in its subtrees, so we find $l = u + w$. Rewriting $(1)$ now gives us:

\begin{align*} n + 1 & = |V_U| + |V_W| + 1\\ & = (2u - 1) + (2w - 1) + 1\\ & = 2(u + w) - 1\\ & = 2l - 1 \end{align*}

Which is exactly the proof for $P(n+1)$. QED

Corollary: Two full binary trees with the same number of leafs will have the same number of nodes.

$\endgroup$
  • $\begingroup$ And what would the question be? $\endgroup$ – cronos2 Oct 23 '17 at 8:40
  • $\begingroup$ @cronos2 Any feedback for the proof (style, correctness of course) would be appreciated. $\endgroup$ – Max Oct 23 '17 at 9:14

Your Answer

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

Browse other questions tagged or ask your own question.