# 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?

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?

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.