The Gateway to Computer Science Excellence
+23 votes

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

  1. $x(n-1) +1$
  2. $xn-1$
  3. $xn +1$
  4. $x(n+1)$
in DS by
edited by | 3.8k views

sum of degree$:l+(x-1)(n+1)+n=2e$

sum of degree$:l+xn+x-1=2e$

# of edges e$=\dfrac{l+xn+x-1}{2}$

and also # of edges in a tree $=(l+x)-1$

$\therefore \dfrac{l+xn+x-1}{2}=l+x-1$

Most easiest way is to simply draw a $3-ary$ tree and verify the options.

8 Answers

+32 votes
Best answer

Answer : $\rightarrow$ (A)

$x(n-1) +1$

Originally when we have root , there is only $1$ node, which is leaf. (There is no internal node.) From this base case "+1" part of formula comes.

When we $n$ children to root, we make root internal. So then Total Leaves $= \ = 1(n-1) + 1 = n$.

In complete $n$ ary tree every time you add $n$ children to node, you add $n-1$ leaves & make that node to which you are inserting childen internal.( $+n$ for leaves, $-1$ for node which you are attaching ). So if you had originally few leaves, you add $n-1$ "New" leaves to them. This is how $x(n-1) +1$ makes sense.

edited by
let d be the no of leaves in this complete n ary tree.

Now, total no of degrees of a n ary tree is = 1*n+(x-1)(n+1)+d*1

Now this is because for root there is 1 node and it has n children so degree n now here it is mentioned that there  are x is the total no of internal nodes we know that internal nodes include root as well as all nodes excluding the leaves so we can get that (x-1) is the no of nodes of this type and they have each (n+1) degree and d is the no of leaf nodes they have degree 1 each.

So we get that the total no of degrees =


And the total no of nodes= d+(x-1)+1(for root)=d+x

Now the  no of edges = ( n*1+(x-1)(n+1)+d) /2 (by formulae)........(1)

now no of edges for a tree is= total no of nodes -1

total nodes= 1+ d+(x-1)=x+d

so total edges= (x+d-1).............(2)

Now equating 1 and 2 we get,


d= 1+(x)(n-1) option A.
+15 votes

As they said in question A complete n-ary tree is one in which every node has 0 or n sons.

lets take few case's and analyze them 

if we consider n = 2 (A Binary tree in place of n-ary tree See figure 1)

if we consider n = 3 (A 3-ary tree in place of n-ary tree See figure 2)

if we consider n = 4 (A 4-ary tree in place of n-ary tree See figure 3)


Type of Tree Internal Node (x) Leaf Nodes
Binary 3 4
3-ary 3 7
4-ary 3 10
5-ary 3 13

In Given Options put the values of internal nodes and type of tree and get the relation

    x(n-1)+1     xn-1     xn+1    x(n+1)
3(2-1)+1 = 4  3*2 - 1 = 5 3*2+1 = 7 3(2+1) = 9
6+1 = 7 8 10 12
10 11 13 15

Answer : Option A

edited by
+6 votes
if 1-ary tree and x is internal node then no of leave is 1

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

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

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

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

so ans is A.)
+6 votes


i = # internal nodes

l = # leaves

n = total # nodes 

then for m-ary tree

total # nodes(n)  = m* i + 1.......................(1)   

also u know  total # nodes(n) = i + l............(2)

now u use these two formula

n x + 1 = x + l

so l = x * (n-1) + 1

+5 votes
Each of the $x$ internal nodes has exactly $n$ edges connected to it. So there are $xn$ edges in the tree. Some of these edges have other internal nodes at the other end and some have leaves at the other end. Except for the root, all other internal nodes are at the other end of an edge starting at an internal node. Thus to get the number of leaves we compute the number of edges with leaves at the other end. We do this by subtracting $x-1$ from $xn$. Hence the formula is $xn - (x-1)$.
+2 votes
Ans is A
0 votes
A complete n-ary tree  has x number of internal nodes. Each such internal nodes has n children, Now except root node every other node(may be leaf or internal) is a children of some other internal node, there are nx numbers of such nodes(x internal nodes, each having n children, so total nx), now if we add 1 (for root)  to nx , which is nx +1 ,we will get total number of nodes in the tree.

Total number of nodes= nx +1 ,   number of external nodes= x ,  So, total leaves= nx+1-x = x(n-1) +1
0 votes

Option A,by sum of degree theorem 

edited by

Related questions

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
52,315 questions
60,436 answers
95,257 users