Test by Bikram | Mock GATE | Test 4 | Question: 31

Question

An $m-ary$ tree is a tree in which every node has at most $m$ children. 
In an $m-ary$ tree with $p$ nodes and height $l$ $($starting from $0)$, which of the following is the tightest upper bound for the maximum number of leaves as a function of $l$, $m$, and $p$?

• A.     $\lg m \times p$
• B.     $\lg m \times l \times \lg p$
• C.     $l^m$
• D.     $m^l$

Answer 1

For the maximum number of children to leaf nodes, we have to attach  'm' children to every non-leaf nodes.

Height =0 Maximum Number of node= m^0=1

Height =1 Maximum Number of node= m^1=m

Height =2 Maximum Number of node= m^2

               .

               .

Height =l Maximum Number of node= m^l