2
$\begingroup$

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.

$\endgroup$
6
  • 1
    $\begingroup$ What is an external node? This is not standard terminology. $\endgroup$ Dec 1, 2022 at 6:38
  • $\begingroup$ @Yuval Filmus The term external node is used as a synonym for a leaf node in my book. $\endgroup$
    – Ruperrrt
    Dec 1, 2022 at 8:50
  • $\begingroup$ Please edit your question to use standard terminology; or, failing that, make it self-contained and contain a definition of "external node" before first use. Don't put clarifications in the comments -- we want questions to be able to stand on their own, so people don't have to read the comments to understand what is being asked. Our goal is to build up an high-quality archive of knowledge, in the form of questions and answers. $\endgroup$
    – D.W.
    Dec 2, 2022 at 5:44
  • $\begingroup$ We discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors. See here and here. Can you edit your post to ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. $\endgroup$
    – D.W.
    Dec 2, 2022 at 5:46
  • 1
    $\begingroup$ A reasonable first check might be to write a program to enumerate all binary trees (up to some size bound -- say, with at most 8 leaves) and check whether your proposition seems to hold for them. $\endgroup$
    – D.W.
    Dec 2, 2022 at 5:47

1 Answer 1

1
$\begingroup$

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$.
$\endgroup$
1
  • 1
    $\begingroup$ Your solution is straightforward. Great! Reading it, I've noticed that the second part of my proof (after the induction) does not account for binary trees that have an odd number of nodes. They need to have at least two nodes with a single child to be improper. Thus, the general structure of a binary tree with a maximum of external nodes, which I've tried to establish by induction, would have to be adjusted accordingly to satisfy both requirements. $\endgroup$
    – Ruperrrt
    Dec 3, 2022 at 11:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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