recategorized by
4,684 views
0 votes
0 votes
In a 3-array tree if internal nodes have exactly 3 children,the number of leaf nodes will be  __ ?

Does it vary for binary tree?

What do you mean by internal nodes? Non root node and leaf node?
recategorized by

2 Answers

1 votes
1 votes

Formula for Leaf Nodes= I(N-1)+1

I---internal nodes

N---n array tree i.e 3

Hence, Leaf Nodes=        3(3-1)+1

                                  =        3×2+1 = 7 nodes

 

0 votes
0 votes

1. Internal node means non leaf node.

we have for n ary tree

no of leaf node=X(n-1)  +1  [By hand shake degree theorem]

where X =no of internal node 

So for your question n=3 =>no of leaf node=2*X + 1

it will be [X(2-1) +1 =X+1] for binary tree n=2.

Related questions

2 votes
2 votes
2 answers
1
0 votes
0 votes
5 answers
2
radha gogia asked Sep 30, 2015
1,607 views
If I am given an array $X$ of $n$ distinct integers which is interpreted as a complete binary tree, so if the parent is at index $i$, then it's left child would be at ind...