The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+11 votes
1k views

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

 

asked in DS by Veteran (67.7k points) | 1k views

6 Answers

+15 votes
Best answer

Answer :->

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.

 

answered by Veteran (46.8k points)
selected 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 =

1*n+(x-1)*(n+1)+d*1

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=(nx-x+1)

d= 1+(x)(n-1) option A.
+6 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

 

 

answered by Veteran (43.6k points)
edited by
+2 votes
Ans is A
answered by Boss (6.4k points)
+2 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.)
answered by Boss (9.9k points)
+2 votes

let

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

answered by Veteran (10.6k points)
0 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)$.
answered by Junior (507 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

29,158 questions
36,985 answers
92,166 comments
34,824 users