Improper binary tree: maximum number of external nodes
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. 743
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)=2i+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. 743