The following shows how to figure out the total number of levels we have in a perfect binary tree from the total number of nodes. We went over this in lecture while ago and you did a proof using PMI (principal of mathematical induction). Please understand this before you work on the problem in the following sections since you will use the same technique.

We have seen the above formula for a perfect (completely full) binary tree many times already. Now lets do the same for M-ary trees.

1. M = 3. Come up with a formula like this that tells us the total number of levels (B) in a perfect tri-ary tree (completely full meaning each node has 3 children) from the total number of nodes (N). Notice each node contains 2 keys/elements. N here is not the number of keys. Please draw a picture as well. You need to show all the process.

2. M =4. Do the same.

3. M = 5. Do the same.

4. What is the general formula that tells us the total number of levels in a perfect M-ary tree from the total number of nodes, N?

5. What is the general formula that tells us the total number of levels in a perfect M-ary tree from the total number of keys/elements, K? In a M-ary tree, each node can have multiple elements. Assume the array in each leaf node is full.

6. Prove your answer to #1 using PMI (principal of mathematical induction). We did a proof for the height of a perfect (completely full) binary tree for a past assignment. You could mimic that.

perfectiy full Binary tree \# of nodes at this level 2122Inthistrel,wehave3levels.B=3thenextfictionallevel Fictional =3 call this ' B ' level. B= the total \# of levels in the tree This level would have 2B nodes \begin{tabular}{ll} The can test this formula by \\ Total \# of Nodes in the tree & We wald have 2B nodes the above tree. Plug in B=3,N=7,7+1=23V \\ \hline \end{tabular} If we want to figure out how many levels we have in the tree from N, 2B=N+1B=log2(N+1) perfectiy full Binary tree \# of nodes at this level 2122Inthistrel,wehave3levels.B=3thenextfictionallevel Fictional =3 call this ' B ' level. B= the total \# of levels in the tree This level would have 2B nodes \begin{tabular}{ll} The can test this formula by \\ Total \# of Nodes in the tree & We wald have 2B nodes the above tree. Plug in B=3,N=7,7+1=23V \\ \hline \end{tabular} If we want to figure out how many levels we have in the tree from N, 2B=N+1B=log2(N+1)