Sorted List To BST

if integers from 1 . . . n were inserted (as keys) in increasing order into a binary heap. There is an ordering of the same keys, so that if they were inserted into a binary search tree, the shape of the tree would be identical to that of the heap. Determine the first value to be inserted into the binary search tree to achieve this.

If we were to insert the values 1, 2, 3, 4, 5 into a binary heap,

                   1
                  /  \
                 2    3
                / \
               4   5

In order for a BST containing the same keys to have that shape, they must be stored as shown in the figure below:

image

So, we conclude that we must insert the 4 first, since it is located at the root of the BST.

Define identical shape :slight_smile:

I would say it’s impossible for any sequence with n > 3… though I might be wrong.