# 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

## Answers

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?