19 2 draw all binary search trees that can result from insertingpermutations of 1 2 4945860

19.2 Draw all binary search trees that can result from insertingpermutations

of 1, 2, 3, and 4. How many trees are there? What are theprobabilities

of each tree’s occurring if all permutations are equally

likely? Assume in each case that you are inserting the items into aBinary Search tree that is initially empty. There are of course 4!permutations, but in many cases multiple permutations lead to thesame tree. For example, 2134 and 2314 lead to the same tree (2 isthe root, 1 is 2’s left child, 3 is 2’s right child, 4 is 3’s rightchild. That’s why different trees have different probabilities(each permutation has probability 1/24, but some trees come frommultiple permutations; the total of all of the probabilities shouldbe 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 . . .