19.2 Draw all binary search trees that can result from inserting permutations of

Question

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 tree’s 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 2’s left child, 3 is 2’s right child, 4 is 3’s 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

Explanation / Answer

So as we told, there can be 4! = 24 combinations in total, but out of them, there can be repeated combinations, which will result into the same tree...

Algorithm:
Now in order to make a tree, You need to consider each number one by one as the root node and then recursively construct the left and right subtree with the remainig numbers...

like if 2 is the root node, then left subtree can be constructed using 1, while right can be constructed using 3 & 4. Now in right subtree, again either 3 can be root, or 4 can be root in right subtree.

In above gven way, we can construct the trees. The list of insertion orders which will result in unique tree is as below:

=================================================
1234 (1), 1243 (1), 1324 (2), 1423 (1), 1432 (1),
2143 (3), 2134 (3),
3214 (3), 3124 (3),
4321 (1), 4312 (1), 4213 (2), 4123 (1), 4132 (1)

=================================================

Here 2143(3) means there are 3 combinations out of 24, which will result in same tree, which we get by inserting 2->1->4->3 in order.. Hence the frequency of this tree is 3 out of 24.

To calculate the probability of each kind of tree, we can divide the frequency by 24, and we will get the probability.

Like tree 3124 has a probability of 3/24, or 1/8 in simple terms.

PLease upvote if you understood the solution.. Do comment if something is not clear.

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.