1
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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