[SOLVED] When would a 2-3-4 tree not have the same structure?

When would a 2-3-4 tree not have the same structure?

I just saw this question get asked in a data structure textbook I'm using and the question goes

Give an example to show that the following claim is wrong: "A 2-3-4 tree storing a set of entries will always have the same structure, regardless of the order in which the entries are inserted."

I know the best case is O(log n) and it better than using the BST but that's about it and I can't seem to find a plausible explanation. How can this statement be proven wrong?

Solution

If you make a tree with some leaves full and some leaves not, then where you put the next node determines whether or not another leaf will split.

So, if we start out by inserting 2,3,4,5, then the root will split into a new root with 2 leaves. one will have 2 values and one will have 1. Then we insert 1,6, and one of those leaves will be full:

      3
     / \
  1,2   4,5,6

Now, if we insert 0, nothing will split, but if we insert 7, the right leaf will split.

The actual numbers don't matter, of course, just how the insert order relates to their sorted order, so we can make these 2 different trees with the same elements. For the tree on the left, I inserted 2,3,4,5,1,6,7, and for the one on the right I inserted 3,4,5,6,2,7,1

      3,5               4
     / |  \          /     \
  1,2  4  6,7     1,2,3   5,6,7