19.2 Draw all binary search trees that can result from inserting permutations of 1, 2, 3, and 4. How many trees are there? What are the probabilities of each trees occurring if all permutations are equally likely?

Assume in each case that you are inserting the items into a Binary Search tree that is initially empty. There are of course 4! permutations, but in many cases multiple permutations lead to the same tree. For example, 2134 and 2314 lead to the same tree (2 is the root, 1 is 2s left child, 3 is 2s right child, 4 is 3s right child. That's why different trees have different probabilities (each permutation has probability 1/24, but some trees come from multiple permutations; the total of all of the probabilities should be 1). As another example, the permutation 2413 leads to the tree (expressed in "displayable" notation) chars="2143", children="20L0".

Draw the tree and state the possibilities