## n-ary Tree

Question 1 |

A complete n-ary tree is a tree in which each node has n children or no children. Let I be the number of internal nodes and L be the number of leaves in a complete n-ary tree. If L = 41, and I = 10, what is the value of n?

3 | |

4 | |

5 | |

6 |

Question 1 Explanation:

L = (n-1) * I + 1

L = No. of leaves = 41

I = No. of Internal nodes = 10

41 = (n-1) * 10 + 1

40 = (n-1) * 10

n = 5

L = No. of leaves = 41

I = No. of Internal nodes = 10

41 = (n-1) * 10 + 1

40 = (n-1) * 10

n = 5

Question 2 |

A complete n-ary tree is one in which every node has 0 or n sons. If x is the number of internal nodes of a complete n-ary tree, the number of leaves in it is given by

x(n-1) + 1 | |

xn - 1 | |

xn + 1 | |

x(n+1) |

Question 2 Explanation:

No. of internal node = x

Let no. of leaf nodes = L

Let n

So, L+x = n

Also for n-ary tree with x no. of internal nodes, total no. of nodes is,

nx+1 = n

So, equating (I) & (II),

L+x = nx+1

L = x(n-1) + 1

Let no. of leaf nodes = L

Let n

_{t}be total no. of nodes.So, L+x = n

_{t}-----(I)Also for n-ary tree with x no. of internal nodes, total no. of nodes is,

nx+1 = n

_{t}-----(II)So, equating (I) & (II),

L+x = nx+1

L = x(n-1) + 1

There are 2 questions to complete.