The Gateway to Computer Science Excellence
0 votes
668 views
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?
in DS by | 668 views
0
if total node is $N$

$n_l = \frac{2N+1}{3}$ ?
0
I dont know the answer.
0

see this

 

0
Is root node counted as internal node?

Btw what software did you use to draw the graph? Paint?
0

@sripo root node is also an internal node unless it is the only node in the tree

0
Yes i used paint.

2 Answers

+1 vote

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

 

by
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.

by
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
52,375 questions
60,571 answers
201,973 comments
95,387 users