Given a 2-3 tree, How can we find a possible insertion order?
so say you are given a 2-3 tree, complete with nodes and a couple of levels. How could you find one of the several possible insertion orders/sequences that give you the resulting tree?
No need for code, just a paper task. I'm certain (praying) it isn't a case of simple trial and error.
A similar question was asked here, but no reply
I'm new to this subject, but I'll take a crack at it.
All we have to do is find a way to take one step backward. That is, to choose a value that may have been the last one added, and deduce what the previous tree must have been.
A new value is added to a leaf; either the leaf had one value (and now has two), or it had two and the new value caused a split. A split will propagate up the tree until it stops either by creating a 3-node or a new root 2-node.
So here's a way to choose a value that may have been the last one added. If there are any two-value nodes in the tree, pick one of the lowest ones; either value in that node may have been the last one. If there are no two-value nodes in the tree, then any value in the tree may the value in the root node must have been the last one.
(That's not exhaustive, there are other possibilities, but we're trying to find a candidate, not all candidates.)
Once you've chosen a value, removing it by unsplitting down to a leaf is pretty straightforward.
Does that suffice, or should I explain in more detail?