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.