Number of ways of inserting into a BST



Really good question. It is basically asking how many different ways you can insert into the BST such that figure given is obtained always.

Clearly you have to insert 3 before any other node.

Then after inserting 3, the constraints are:
1 should be inserted before 2
5 should be inserted before 4 and 6

So if we go by permutations and combination, the question simply reduces to "no of different permutations of 12456 in which 1 should be followed by 2 , 5 should be followed by 4 and 6 always’

= total permutations/(restricted permutations)

= 5!/2!3!

= 10

Now in the above calculation we have also restricted the movement of 4 and 6. Now they can arrange among themselves in 2! ways.

So final ans is 10*2! = 20

Alternatively, you can write all the possible permutations using brute force method.