Applied Test series: DS

Question

The number of insertion sequences of the numbers {1,2,3,4,5,6,7} which would lead to the following BST

How to tackle this kind of problem. Anyone!

Comments

Updating a solution here after analysis by my side again:

4 is fixed as root

1: if 426 comes then remaining nodes # of insertion possible is 4! ways

2: if 462 comes then remaining nodes # of insertion possible is 4! ways

3: if 42(31)6(57) comes then # of insertion possible is 2!*2!= 4 ways

4. if 42(3)6(1)(57) comes then # of insertion possible is 2!*2!= 4 ways

mirror image cases of 3 and 4 will have same cases

Total cases = 24+24+4+4+4+4= 64

5. if 4216(57)3 comes then 2! = 2 cases

or 4236(57)1 comes # of insertion possible is  2! = 2 cases

6. if 4652(13)7 comes then # of insertion possible is  2! = 2 cases

or 4672(13) comes then 2!=2 cases.

from step step 5 and 6 total nos = 2+2+2+2 = 8 cases

Similarly other 8 sequences are there

 

So Total would be = 64 + 8+8 = 80 cases

Answer 1

Answer should be 80

 

4 should be the first element in any sequence without any ambiguity.

Now we have 6 slots where in all slots 2 should come before 1 and 3, and 6 should come before 5 and 7.

 

Now considering the positions of only 2, 1 and 3 in the insert sequence.

2 would have 4 places out of 6

Say 2 is in the 4^th position

*

*

*

2

*

*

 

Out of the positions indicated by ‘*’, only the last two positions are valid for 1 and 3

thus the total number of such combinations is 2P2. Where P means permutation and mPn means $\frac{m!}{(m – n)!}$

Now considering all the other combinations 

*

*

2

*

*

*

Here we would have 3P2 combinations

And so on an so forth.

Thus the total number of sequences = 5P2 + 4P2 + 3P2 + 2P2 = 40

Now after filling up the three positions for 2, 1 and 3 we would have only 3 slots left 

There will be a least index among the three slots which would be necessarily filled up by 6 and the remaining 2 slots would be filled by 5 and 7, thus giving 2P2 permutations.

 

Thus total number of sequences = (5P2 + 4P2 + 3P2 + 2P2) * 2P2 = 40 * 2 = 80

 

Answer 2

Total ways = C(3 + 3, 3) × (ways of left) × (ways of right)
           = C(6, 3) × (left ways) × (right ways)
           = 20 × (left ways) × (right ways)
 

ways of left (2-root) = C(1+1, 1) × (ways of 1) × (ways of 3)
                      = C(2,1) × 1 × 1 = 2
 

ways of right (6-root) = C(1+1, 1) × (ways of 5) × (ways of 7)
                       = C(2,1) × 1 × 1 = 2
 

Total ways = 20 × 2 × 2 = 80