recategorized by
1,179 views
1 votes
1 votes
Suppose there are $11$ nodes in a binary tree. Find the number of unlabeled binary trees if the number of nodes either in the left sub tree or in the right sub tree is divisible by $4.$
recategorized by

1 Answer

Best answer
5 votes
5 votes

For the number of nodes to be divisible by 4, we can partition the nodes in 6 ways

The partitions can be made from a total of 10 nodes because 1 node will be occupied by the root.

Partitions:

Left Sub-tree = 4, Right Sub-tree = 6 OR Left Sub-tree = 6, Right Sub-tree = 4

Left Sub-tree = 2, Right Sub-tree = 8 OR Left Sub-tree = 8, Right Sub-tree = 2

Left Sub-tree = 0, Right Sub-tree = 10 OR Left Sub-tree = 10, Right Sub-tree = 0

Now, we have to calculate in how many ways can we construct an Unlabelled binary tree with the available number of nodes, and that is given by $(2n)Cn/n+1$

if you apply it here you will get:

$2*((8C4)/5)*((12C6)/7) + 2*((16C8)/9)*((4C2)/3) + 2*((20C10)/11)*$

This will evaluate to 43008

selected by
Answer:

Related questions

4 votes
4 votes
1 answer
3
3 votes
3 votes
5 answers
4
srestha asked May 22, 2019
1,794 views
Consider the following function height, to which pointer to the root node of a binary tree shown below is passedNote that max(a,b) defined by #define max(a,b) (a>b)?a:b.i...