edited by
12,853 views
17 votes
17 votes
A $3-\text{ary}$ tree is a tree in which every internal node has exactly three children. Use induction to prove that the number of leaves in a $3-\text{ary}$ tree with $n$ internal nodes is $2(n+1)$.
edited by

3 Answers

Best answer
18 votes
18 votes
Number of nodes at level $i =3^i$

Let height of the tree be $h$

So total no of internal nodes, $n=3^0+3^1+3^2+\dots +3^{h-1}=\frac{3^{h}-1}{2}$

$2n=3^{h}-1$

Number of leaf nodes $=3^h =2n+1=2(n-1)+3$

Let us prove by induction

Base case

$n=1$ (one internal node i.e., root node)

No of leaves $=2(1-1)+3=3$

Let it be true for $n$ internal nodes

Now we prove for $m$ nodes where $m=n+1$

We have $L(m)=2(n+1-1)+3$

Also $L(m)=L(n)+3-1\\=2(n-1)+3+3-1\\=2n+3$

So if $L(n)$ is true then $L(n+1)$ is also true

Hence proved by induction.
selected by
4 votes
4 votes
Lets try to get the formula by forming the recurrence relation.
Let T(n) denote the number of leaves of a 3 ary tree having ‘n’ internal nodes.
Base case : T(1) = 3
Now if we take one of the leaf nodes and convert it to internal node by adding 3 children to it, then no of leaves would decrease by 1 (since one leaf got converted to internal node) and also increase by 3(owing to the 3 new leaves created by leaf which converted to internal node)
So now T(n)=T(n-1)+3-1
                    =T(n-1)+2
                    =T(n-2)+2*2
                    =T(n-3)+3*2
                    ……
                   =T(n-k)+k*2

 when n-k=1, k=n-1, also T(n-k)=T(1)=3

                   =3+2*(n-1)
                   =2n+1
1 votes
1 votes
The question is wrong . Since the Question asks for "A 3−ary3−ary tree is a tree in which every internal node has exactly three children".

Proof :

N3 : Number of internal nodes with 3 children

N0 : Number of nodes with 0 children i.e. number of leaves

N : Total number of nodes

1) According to the question , since a node can only have 3 children or none this means , N = N3 + N0

2) Every node with 3 children will contribute to 3 edges connecting nodes to the next level , 3 * N3 = E (Total edges) = N - 1 (edges of a tree)

Now solving N = N3 + N0 and 3 * N3 = N - 1 we get N0 = 2 * N3 + 1 (Ans)

hence then answer should have been 2*n + 1 and not 2 * (n - 1)
edited by

Related questions

18 votes
18 votes
2 answers
1
Kathleen asked Oct 5, 2014
1,966 views
Use the patterns given to prove that$\sum\limits_{i=0}^{n-1} (2i+1) = n^2$(You are not permitted to employ induction)Use the result obtained in (A) to prove that $\sum\li...
29 votes
29 votes
6 answers
3
Kathleen asked Oct 5, 2014
4,888 views
An array $A$ contains $n$ integers in non-decreasing order, $A \leq A \leq \cdots \leq A[n]$. Describe, using Pascal like pseudo code, a linear time algorithm to find $...