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$
$\endgroup$
5
-
$\begingroup$ What do you means with complete? Is the number of children specified (you only mentioned not binary)? $\endgroup$– Narek BojikianJan 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$– icebitJan 28, 2020 at 11:48
-
$\begingroup$ But what do you mean then with "not necessarily a binary" $\endgroup$– Narek BojikianJan 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$– icebitJan 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$– STanjaJan 28, 2020 at 18:06
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
Hint:
Try the case $h=1$. What's the minimum? What's the maximum?
$\begingroup$
$\endgroup$
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:
- 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$
- Now you would use the following equation to calculate and find the internal nodes (I) from vertices (n)
$I = \frac{n-1} m$
- 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$
