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?

  • $\begingroup$ What do you means with complete? Is the number of children specified (you only mentioned not binary)? $\endgroup$ Jan 28 '20 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 '20 at 11:48
  • $\begingroup$ But what do you mean then with "not necessarily a binary" $\endgroup$ Jan 28 '20 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 '20 at 14:26
  • 2
    $\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 '20 at 18:06


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


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.