Improper binary tree: maximum number of external nodes

Question

The term external node is used as a synonym for a leaf node in the following. A binary tree shall be called proper if each node has either zero or two children. If it is not proper, it shall be called improper.

I need to determine the maximum number of external nodes in an improper binary tree. Here is my current attempt to solve this problem:

My intuition is that, in general, a binary tree has a maximum number of external nodes when it has at most one node with a single child. Consequently, my first step is to prove that assumption by induction.

Proposition: A binary tree $T$ of $n$ nodes achieves a maximum number of external nodes when it has at most one node that a single child.

Base case ($n=1$): A tree with just a root node has no nodes with just a single child and with one external node it also has the maximum number of external nodes for a tree with one node.

Induction step: Let $T$ be a tree with $n+1$ nodes which has at most one node with a single child.

If $T$ has a node with a single child, we remove that child to get a tree with $n$ nodes that has a maximum $m$ of external nodes. Adding the removed child node back to the tree, we still have a total number of $m$ external nodes, which also is the maximum for a tree with $n+1$ nodes (I think, for this reasoning to be fully valid, I would have needed to show that any tree with $n$ nodes that does not fullfill above requirement cannot have the same number of external nodes and have its external node count incremented when adding a node, but the tree we're looking at has not). Otherwise, removing an arbitrary external node gives us a tree with $n$ nodes which has exactly one node with just a single child. This tree has a maximum $m'$ of external nodes. Now, adding the removed node back to the tree, its external node count becomes $m'+1$ which has to be the maximum for a tree with $n+1$ nodes, as adding a node can only increase the number of external nodes by at most one.

As the next step, we can observe that an improper binary tree that satisfies the above-mentioned requirement becomes a proper binary tree when removing its only non-root node without a sibling (there has to be exactly one). We know that in a proper binary tree with $i$ internal nodes there are $e=i+1$ external nodes. When putting the removed node back into its place we get a tree with $i'=i+1$ internal nodes and still $e$ external nodes. Thus, we have a tree with a total of $n=i'+e=(i+1)+(i+1)=2*i+2$ nodes. The number of internal nodes is $i'=(n-2)/2+1=n/2$ and the number of external nodes is $e=n/2$. Therefore, the maximum number of external nodes in an improper binary tree with n nodes is $n/2$.

Edit: I'm particularly unsure about the necessity of proving, by induction, the general structure of a binary tree that has a maximum of external nodes. I need help in writing a proof that is more formal and straight to the point.

Answer 1

Your reasoning looks on the right track. However, somewhere along the way, it loses track of the correct parity of numbers and the exact number of nodes that have $1$ child. More case-by-case analysis may be in need.

---

Here is a simpler and clearer way with combinatorics flavor, i.e., using double counting to obtain relations between variables.

Suppose we have an improper tree with $n$ nodes.

• Let $n_0$ be the number of nodes without children, i.e., external nodes.
• Let $n_1$ be the number of nodes with $1$ children. $n_1\ge1$ since the tree is improper.
• Let $n_2$ be the number of nodes with $2$ children.

Then $n= n_0+n_1+n_2$, since both sides are the total number of nodes in the tree.

The number of all child nodes, i.e., nodes in the tree that are children of another node is $n-1$ since every node except the root is a child node. On the other hand, the parent of a child node has either $1$ or $2$ children.

• the number of child nodes that have a parent with 1 children is $n_1$,
• the number of child nodes that have a parent with 2 children is $2n_2$.

Hence $n-1=n_1+2n_2$. Replacing $n_2$ with $n-n_0-n_1$, we get $n-1=n_1+2(n-n_0-n_1)$. So, $$2n_0=n-n_1+1.$$

• If $n$ is even, then the least possible value of $n_1$ is $1$, which can be attained. The maximum number of external nodes $n_0=\frac n2$.
• If $n$ is odd, then the least possible value of $n_1$ is $2$, which can be attained. The maximum number of external nodes $n_0=\frac{n-1}2$.