1,090 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 ___

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

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

1 votes
1 votes

→ 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

2 votes
2 votes
3 answers
1
Arjun asked Oct 10, 2016
591 views
Consider a complete graph on 10 vertices. Minimum no. of edge removals required to make a tree out of it will be ____
0 votes
0 votes
3 answers
2
Arjun asked Oct 10, 2016
617 views
Consider a complete graph of 10 vertices. The minimum no. of edge removals required to make the graph disconnected is ______
0 votes
0 votes
2 answers
4
Arjun asked Oct 10, 2016
521 views
Consider the following declaration of a two dimensional array in C:char a[1000][40];Assuming that the main memory is byte addressable and that the array is stored startin...