The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+17 votes

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$?

  1. $3$
  2. $4$
  3. $5$
  4. $6$
asked in DS by Veteran (69k points)
edited by | 2.9k views
if 1-ary tree and 'i' is internal node then no of leave is 1

if 2-ary tree and 'i' is internal node then no of leaves are (i+1)

if 3-ary tree and 'i' is internal node then no of leaves are (2i+1)

if 4-ary tree and 'i' is internal node then no of leaves are (3i+1)

if n-ary tree and 'i' is internal node then no of leaves are (n-1)i+1

given that leaves L=41,internal node i=10,,

then L=(n-1)i+1




5 Answers

+20 votes
Best answer

If you do little bit experiments on no of leaves, Internal nodes, you will realize that they have equation like following :-

No of leaves $(L) = (n-1) *$ Internal Nodes $(I) + 1$

here we need to find $n$.

Putting values

$41 = (n-1) * 10 + 1$

$(n-1) * 10 = 40$

$n-1 = 4$

$n = 5$

So answer = C

answered by Veteran (49.5k points)
edited by
+24 votes

Sum of degrees in tree = L +  I * (n+1) - 1 = 10n + 50 (Each leaf node has degree 1 and all internal nodes have degree k+1, except root which has degree k)

So, number of edges = 5n + 25 (Number of edges in a graph (hence applicable for tree also) is half the sum of degrees as each edge contribute 2 to the sum of degrees)

In a tree with n nodes we have n-1 edges, so with 41+10 = 51 nodes, there must be 50 edges. 

So, 5n + 25 = 50

5n = 25 => n = 5


answered by Veteran (346k points)
+10 votes

Full m-ary tree means : Every internal node have exactly m children. Other way, each node has zero or m children only. 

Some of the full m-ary trees.

T1 (m=2) ,  T2 (m=3) , T3 (m=5)  are full but Tis not.

In this question, how they define complete means the full m-ary tree. We have n-ary tree and Internal nodes ( I ) = 10 , Leaf nodes ( L ) = 41

$n = L+ I \\ =>n = 51 \\ =>n*10+1 = 51 \\ =>n = 5$

answered by Veteran (59.9k points)
edited by
same way.. i have done
+6 votes

Total number of internal nodes = $I=10$
Total number of leaf nodes = $L=41$

for a $n-ary$ tree, levels starts with $0$ and at each level there are $n^k$ nodes; where $k$ it the level number.

\[\begin{align*} \text{total number of nodes} - L &= I \\ \left( 1 + n^1 + n^2 + \dots + n^k \right) - L &= I \\ \left( 1 + n^1 + n^2 + \dots + n^k \right) - 41 &= 10 \\ \left(n^1 + n^2 + \dots + n^k \right) &= 50 \\ \frac{n(n^k-1)}{n-1} &= 50 \qquad \text{;on putting }n=5 \\ n^k &= 41\\ \end{align*}\]

where, $n^k$ represents number of nodes in last level i.e. leaf nodes, so on taking option C verifies it.

Hence, answer = option C

answered by Veteran (31k points)
+1 vote
for this type of question, don't remember formulas simply learn derivations

total number of nodes (N) = internal nodes (n)+ leaf nodes(L)

total  number of edge(E)= N-1

so here internal node=10 , leaf nodes=41

so edge(E)= 10+41-1=50

again Edge E= maximum child size of internal nodes* total internal nodes

so, 50= I*10

answered by (113 points)

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

33,687 questions
40,231 answers
38,801 users