0
$\begingroup$

I want to determine the minimum and maximum number of leaves of a complete tree(not necessarily a binary tree) of height $h$.
I already know how to find minimum($h+1$) and maximum($2^{h+1}-1$) number of nodes from the height, but what about leaves? Is there a way to determine them knowing nothing but height of the tree?

$\endgroup$
  • $\begingroup$ What do you means with complete? Is the number of children specified (you only mentioned not binary)? $\endgroup$ – narek Bojikian Jan 28 at 11:39
  • $\begingroup$ @narekBojikian In a complete binary tree every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible.. the number of children is not specified but you can assume a binary tree. $\endgroup$ – icebit Jan 28 at 11:48
  • $\begingroup$ But what do you mean then with "not necessarily a binary" $\endgroup$ – narek Bojikian Jan 28 at 13:03
  • $\begingroup$ That it can be any kind of m-ary tree, i.e. a ternary tree, a binary tree or anything else. The number of children is the irrelevant part of this problem. $\endgroup$ – icebit Jan 28 at 14:26
  • 1
    $\begingroup$ Let's recall the definitions. In an $m$-ary tree, each node has at most $m$ children. In a complete $m$-ary tree, each node (except the leaves) has $m$ children, the leaves have 0 children. In other words, asking what number of children is is very relevant to the question. $\endgroup$ – STanja Jan 28 at 18:06
0
$\begingroup$

Hint:

Try the case $h=1$. What's the minimum? What's the maximum?

| cite | improve this answer | |
$\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.