edited by
14,544 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

5 votes
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)$.
1 votes
1 votes
  1. Assume the degree of leaves to be 0 and not 1
  2. We know degree of internal nodes will be n
  3. Sum of degrees = Leaves * 0 + n * x
  4. Number of edges = Leaves + x – 1
  5. Finally solve , n * x = Leaves + x – 1

 

0 votes
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
Answer:

Related questions

21 votes
21 votes
1 answer
2
Kathleen asked Sep 26, 2014
4,131 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