The maximum number of nodes in tree with $k$ leaves where every internal node has at least two children is $2k-1$. This is clearly true for a complete binary tree but how can you prove it is true in general?
$\begingroup$
$\endgroup$
Add a comment
|
$\begingroup$
$\endgroup$
If the tree has maximal depth of $h$, then at the level $h - 1 $ we can have at most $k/2$ nodes, and hence on the level $h-2$ the number of nodes is bounded above by $k/4$, and so on. We thus get that the number of internal nodes is bounded above by $$ \frac k2 + \frac k4 + ... + \frac{k}{2^{h-1}} < k, $$ and hence can be at most $k-1$. Putting together $k$ leaves, we end up with $2k-1$ nodes.
