insert(tree,item):
|  Input  2-3-4 tree, item
|  Output tree with item inserted
|
|  node=root(tree), parent=NULL
|  repeat
|  |  if node.order=4 then
|  |  |  promote = node.data[1]     // middle value
|  |  |  nodeL   = new node containing node.data[0]
|  |  |  nodeR   = new node containing node.data[2]
|  |  |  if parent=NULL then
|  |  |     make new 2-node root with promote,nodeL,nodeR
|  |  |  else
|  |  |     insert promote,nodeL,nodeR into parent
|  |  |     increment parent.order
|  |  |  end if
|  |  |  node=parent
|  |  end if
|  |  if node is a leaf then
|  |     insert item into node
|  |     increment node.order
|  |  else
|  |  |  parent=node
|  |  |  i=0
|  |  |  while i<node.order-1 and item>node.data[i] do
|  |  |     i=i+1     // find relevant child to insert item
|  |  |  end while
|  |  |  node=node.child[i]
|  |  end if
|  until item inserted