What is the smallest possible depth of a leaf in a decision tree for a comparison sort?

This problem aims to familiarize us with permutations and decision trees. The concepts required to solve this problem are related to algorithms and data structures which include computation, permutation, combination, and decision trees.

In data structures, permutation correlates to the action of organizing all the components of a set into an arrangement or order. We can say that, if the set is already ordered, then the rearranging of its elements is called the process of permitting. A permutation is the selection of $r$ items from a set of $n$ items without a substitute and in order. Its formula is:

$P^{n}_r = \dfrac{(n!)}{(n-r)!}$

Whereas the combination is a method of choosing entities from a group, in which the arrangement of choice is not important. In shorter combinations, it is likely to estimate the number of combinations. A combination is the selection of $r$ items from a set of $n$ items without a substitute irrespective of the arrangement:

$C^{n}_r =\dfrac{(P^{n}_r)}{(r!)}=\dfrac{(n!)}{r!(n-r)!}$

Let’s consider that we have a collection of $n$ items. This implies that there are $n!$ permutations in which the collection can be organized.

Now a decision tree includes a main node, some branches, and leaf nodes. Every inner node represents a test, every branch represents the result of a test, and every leaf node carries a class label. We also know that a complete decision tree has $n!$ leaves but they are not required to be on the same level.

The shortest possible answer to the problem is $n − 1$. To briefly look at this, assume that we carry a root-leaf path let’s say $p_{r \longrightarrow l}$ with $k$ comparisons, we cannot be certain that the permutation $\pi (l)$ at the leaf $l$ is justified the correct one.

To prove this, consider a tree of $n$ nodes, where every node $i$ denotes $A[i]$. Construct an edge from $i$ to $j$ if we compare $A[i]$ with $A[j]$ on the track from the main node to $l$. Remark that for $k < n − 1$, this tree on ${1, . . . , n}$ will not be combined. Therefore, we have two elements $C_1$ and $C_2$ and we assume that nothing is known about the comparative order of collection items indexed by $C_1$ against items indexed by $C_2$.

Hence, there cannot exist a single permutation $\pi$ that arranges all intakes passing these $k$ tests – so $\pi (l)$ is inappropriate for some collections which guide to leaf $l$.

Numerical Result

The shortest likely depth of a leaf in a decision tree for a comparison sort comes out to be $n 1$.

Example

Find the number of ways to arrange $6$ children in a line, if two individual children are constantly together.

According to the statement, $2$ students must be together, thus considering them as $1$.

Hence, the outstanding $5$ gives the configuration in $5!$ ways, i.e. $120$.

Furthermore, the $2$ children can be organized in $2!$ distinct ways.

Therefore, the total number of arrangements will be:

$5!\times 2! = 120\times 2 = 240\space ways$