Binary Decision Tree

Here is a schematic representation of a decision tree corresponding to a comparison-based algorithm based on successive answers to yes/no questions (binary comparisons).

Exercise Draw a decision tree for performing linear search given a target value $x$ over the unordered array $[a_1, a_2, a_3]$.

Solution

Exercise Draw a decision tree for performing binary search given a target value $x$ over the sorted array $[a_1, a_2, a_3]$.

Solution

Exercise Draw a decision tree for performing a generic comparison-based sort algorithm to sort the array $[a_1, a_2, a_3]$.

Solution