1,335 views
4 votes
4 votes

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!

1 Answer

7 votes
7 votes

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 4th 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

 

Related questions

1 votes
1 votes
2 answers
3
rahul sharma 5 asked Oct 6, 2017
781 views
What is the time complexity to delete the root node in right skew tree?I knew the three cases of BST deletion:- 0 child,one child,two child.But how can we handle this par...
2 votes
2 votes
1 answer
4
rahul sharma 5 asked Oct 2, 2017
444 views
What is the worst case time complexity to construct unique BST froma:) Inorder and preordera:) Inorder and postorder