Which is the correct method of insertion into a 2-3 tree?

Question

I was given a question by my class teacher to perform the insertion in a 2-3 tree.

What I did was the upper method. And what he wanted is the method below. Can you please tell me which is the correct method as I've looked onto web and I can see both the method there. But I still don't know why I lost 10 marks! Thanks in advance for help.

Answer 1

Let me start by saying there are many different versions of a 2-3 trees, so it can be confusing. Really they only differ on the way the store values. Some only store values in leafs and other store values in every node.

I believe your teacher is using latter definition of 2-3 trees. So the problem with your tree is the "root" node has the same values as it's children, a node will never share the same values as it's children. Although, I don't think what your teacher supplied is a true 2-3 tree either. A 2-3 tree will split when a node contains 3 values. I would expect below to be the proper output:

Add 4 to tree:

(4)

Add 7 to tree:

(4,7)

Add 6 to tree:

(4,6,7)
*splits*
  (6)
(4) (7)

Once the root node get's 3 values then it splits into a 1-2 tree.

If you were to insert 8:

  (6)
(4) (7,8)

If you were to insert 9:

   (6)
 (4) (7,8,9)
 *push-up*
   (6,8)
(4) (7) (9)

When a non-root node get's 3 values; push middle value up to parent, if pushing up the value the value makes the parent have 3 values then the parent will split.