0
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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.

$\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.