Question

Either draw a full m-ary tree with 84 leaves and height 3,
where m is a positive integer, or show that no such tree
exists.​

Answer 1

additional 87leves and 6height

Answer 2

Answer:

No such tree exists

Step-by-step explanation:

Concept

• Positive integers are all whole numbers, both positive and negative, that are larger than zero and do not include fractions or decimals.

Given

No. of leaves and height of tree

Find

No such tree exists

Solution

Let's suppose that such a tree exists. Recall the theorem that says that: A full m-ary tree with leaves has $n=\frac{(m l-1)}{(m-1)} vertices$ and $i=\frac{(l-1)}{m-1}$ internal vertices.

With the parameters given in the problem, this tree must have $i=\frac{83}{(m-1)} \text { internal vertices. }$

For this to be a number$" k " k \in Z, m-1$ must be a divisor of 83 , otherwise $i \notin Z$.

Since 83 is prime this implicates that m=2 or m=84 becuase$i=\frac{83}{2-1}=\frac{83}{1}=83$ or$i=\frac{83}{84-1}=\frac{83}{83}=1$

If m=2, the maximum number of vertices is 15, one for the root, two at level 1,4 at level 2, and 8 at level 3. Hence m cannot be 2.

If m=84, by step 4, we know that i=1. This means that the root is the only internal vertex. Hence, the height is 1.

From steps 5 and 6 we notice that for a tree with 84 leaves, the real height is 1 , rather than 3 , so this is a clear contradiction.

So no such tree exists

#SPJ3