in DS
566 views
2 votes
2 votes

A $2-3$ tree is a tree such that

  1. all internal nodes have either 2 or 3 children
  2. all paths from root to the leaves have the same length.

The maximum number of nodes of a 2-3 tree having 9 leaves is ___

in DS
by
566 views

1 comment

Answer should be 16.
1
1

3 Answers

9 votes
9 votes
Total node = (Degree of Node) * (No of Node of that degree) + 1
Total Node = Leaf Node + Internal Node

Let number of nodes of degree 2 is n and number of nodes of degree 3 is m,

Total node = 2n + 3m + 1
Total node = 9 + (m + n)

Both are equal so equate them,
2n + 3m + 1 = 9 + (m + n)
n + 2m = 8    

Solution 1 : n = 2, m = 3
Solution 2 : n = 4, m = 2
Solution 3 : n = 6, m = 1
Solution 4 : n = 8, m = 0

Solution 1,2,3 are feasible but out of these three we have to select solution with max number of nodes i.e. solution 3.
Internal nodes are 7 leaf nodes are 9, Total 16 nodes.

Why not solution 4 ??
in question there is one more line "all paths from root to the leaves have the same length." With solution 4 this property violates. In complete binary tree with d depth max no of nodes will be 2^d-1. By putting d = 4 we wont get 16. i.e. max 15 possible. For 16th we have to go to next level and then "all paths from root to the leaves have the same length." violated.

4 Comments

Good explaination Thanks :)
0
0
i can not understand, how you will write

total node=(Degree)*(No. of node of that degree)+1
0
0
I am getting answer as 17 ..can anyone plz help me with this

9 leaf nodes,1 rot node and 7 internal nodes..

please suggest
2
2
edited by

@Nirmalbbll

In trees, #edges = #nodes – 1
In trees, degree of a node = #children of that node
By handshaking lemma, #edges =  For node i = 1 to i = n Σ( #children of a node i)

#edges = degree of a node * #nodes with that degree

#nodes – 1 = 2n + 3m
#nodes = 2n + 3m + 1

NOTE : read “#something” as : number of something

0
0
6 votes
6 votes

Maximum no of nodes would be 16 not 13... had it been asked for min no of nodes than ans would be 13.

4 Comments

edited by

@Kapilp  In answer given by me...all paths from root to leaves is of same lenght (3)

0
0
is answer contain leaves nodes also , or just intern nodes...
0
0
yes, ans should be 16 ..

13  would be ans if all non leaf contains exactly 3 child..
1
1
1 vote
1 vote

→ 2 or 3 child

→ All paths from the root to the leaves have the same length.


                         [] → +1

           []                         [] → +2

    []           []            []           [] → +4

[]  []  []    []    []      []    []     []      [] → +9 leaf nods

→ 16 nodes require

Answer:

Related questions