Question: seven keys 1, 2, 3, 4, 5, 6, and 7 are inserted in some order into an initially empty binary search tree (BST). Specify four insertion orders yielding trees of the maximum height and four insertion orders yielding trees of the minimum height.
I feel struggled about how to insert 4 maximum heights and 4 minimum heights, My idea is to pick up 4 as the root then probably only one minimum height and maximum height? Please share some ideas, Many thanks!
Thinking about how the BST insertion algorithm works could be a good approach to this problem. To generate a maximum height tree, you need to make sure that no node has two children. In a BST, the left subtree will contain keys smaller than the root while the right subtree will have larger keys. So, by choosing the minimum or maximum of the set as the root, you'll achieve your goal: there will be no element to insert to the right (if root is maximum) or to the left (if root is minimum). Then, you continue doing this recursively: in each subsequent insertion, choose either the maximum or the minimum of the remaining items. In each step you'll have two options to choose from (except for the last step, where you'll only have one remaining item), so there are 2⁶ permutations to choose from. For example, 7 1 6 5 4 2 3 or 1 2 3 7 4 6 5.
Now let's analyze the minimum height case. A minimum height tree of 7 keys will be a full tree of height 3. Due to the property mentioned above, this means that the root will necessarily be the middle element, because we need to insert the same amount of elements to the left and to the right. Now we also proceed recursively: on the left we'll have 1, 2 and 3 and 2 will have to be the root of the left subtree, while on the right we'll have 5, 6, and 7 and 6 will have to be the root of the right subtree. The order of insertion of 2 and 6 yields the same result. Next, you need to insert the leaves but in this case there are no restrictions. This means that you'll have only one option for the first item (4), two options for the second (2 or 6) and 4! for the remaining 4, which equals 48 possible permutations. For example, 4 6 2 1 7 5 3 or 4 2 6 1 7 3 5.