562 views

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 ___

### 1 comment

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.

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

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

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

edited

@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

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

by

edited by

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

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

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

→ 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