What is the upper bound on the number of nodes in a tree with n leaves where each internal node has at least two children?

Question

The pieces of information available to us are the number of leaves in a tree and that each internal node must have at least two children. Is there a way to find the upper bound on the total number of nodes in the tree?

Answer 1

Is there a way to find the upper bound on the total number of nodes in the tree?

Yes. There is actually a formula for the exact number: see e.g. these notes:

A full $m$-ary tree with $l$ leaves has $n = \frac{ml - 1}{m - 1}$ vertices and $i = \frac{l-1}{m-1}$ internal vertices.

Here, $m$-ary means that every internal node has between $1$ and $m$ children, and full means that every internal node has exactly $m$ children (the maximum). So in your case, for a full binary tree, just plug in $m = 2$ to these formulas.

---

By the way, to derive such formulas, you can count the number of vertices in the tree in two ways. First, they are either internal or leaves, so $$ n = i + l $$ Second, we can obtain the total number of vertices by adding up the number of children over all nodes, plus the root, so $$ n = 1 + \sum_{v \in V} \text{children}(v) = 1 + mi, $$ because each internal node has $m$ children and leaves have no children. Now set the two equal and we have $$ i + l = 1 + mi, $$ from which we can derive the above results.