edited by
14,549 views
29 votes
29 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)$
edited by

11 Answers

0 votes
0 votes

Recursive solution for this problem:

$T(x) = T(x-1) + n -1$

$T(0) = 1$


$T(x) = T(x-i) + i \cdot (n-1) $

when i=x, we have x-i = 0

$T(x) = T(0) + x\cdot(n-1)$

$ = 1 + x\cdot (n-1)$

Hence option A

0 votes
0 votes
Let #internal nodes = 1 then #leaves = n

#internal nodes = 2 (means one of the leaf out of n leaves become internal node therefore now #leaves=n-1 but cause of  adding one more internal node we again got n more leaves therefore #leaves=n-1+n) then #leaves = n-1+n = 2n-1

#internal nodes = 3 then #leaves = 2n-1-1+n = 3n-2

#internal nodes = 4 then #leaves = 3n-2-1+n = 4n-3

:

:

#internal nodes = x then #leaves = xn-(x-1) = xn-x+1 = x(n-1)+1
0 votes
0 votes
Every internal node adds n leaves & subtracts 1 leave expect for the root.Root as an internal node directly add n leaves & a single node is just a 1 leaf.
Answer:

Related questions

21 votes
21 votes
1 answer
2
Kathleen asked Sep 26, 2014
4,132 views
Derive a recurrence relation for the size of the smallest AVL tree with height $h$.What is the size of the smallest AVL tree with height $8$?
26 votes
26 votes
5 answers
3