2,4 tree with the fewest number of nodes with the given keys

Question

suppose we have a set of keys K = {1, 2, 3, 4, 5, 6,..., 15} and we need to build a two four tree out of this such that:

• CASE1 : the tree has the minimum number of nodes.
• CASE2 : the tree has the maximum number of nodes.

my idea -

a node in the two four tree can have upto 3 keys and 4 children per node, if we need to minimise the number of nodes we need to keep the nodes full as much as possible, but do not seem to be able to find a strategy that will guarantee this.

one way that seemed lucrative was to split the array into three parts and then insert the medians at the root, next the first and the last child are pre-determined and repeat the same process for the rest of the remaining keys.this method also seems to fall short.

we do know that the worst case height for such a structure needs to be near 4 and the best case height to be near 2 (using the 2, 4 tree height properties h ~ log(n))

is there any strategy to approach such problem (any hint would be appreciated)?

Answer 1

To make a 2-4 tree with the smallest number of nodes:

1. Starting with N keys, floor(N/4) of then need to be parents. Choose these keys, as evenly distributed as possible to ensure that there are 2-3 keys on either side of them.
2. Repeat the procedure with the parents, until you have at most 3 keys. Those go in the root.

So starting with 15 keys, you have 12 leaf-level keys in 4 nodes (3 parents). Those 3 parents can go in the root.