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

2 Answers 2

1
$\begingroup$

Hint:

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

$\endgroup$
1
$\begingroup$

For a given height (h) in m-ary tree, you can calculate first the max/main number of nodes and then calculate the leaves according to each situation:

  1. To calculate the max/min number of nodes in m-ary tree use the following equations:

Maximum number of nodes: $\frac{m^{h+1}-1} {m-1}$

Minimum number of nodes: $(mh)+1$

  1. Now you would use the following equation to calculate and find the internal nodes (I) from vertices (n)

$I = \frac{n-1} m$

  1. You would have Internal nodes (I), and vertices (n). So finally you would use the following equation to find the leaves (L)

$L = n - I$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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