2-3 Insertion

Learn how insertion is done in 2-3 trees based on multiple scenarios. This is explained in the insertion algorithm.

Introduction

Insertion in 2-3 trees is different from binary search trees. In 2-3 trees, values are only inserted at leaf nodes based on certain conditions. As discussed before, the insertion algorithm takes O(Logn)O(Logn) time where n is the number of nodes in the tree. Searching an element is done in Log(n)Log(n), and then insertion takes a constant amount of time. Overall, the time complexity of the insertion algorithm is O(Logn)O(Logn). Let’s see how it works!

Insertion algorithm

The insertion algorithm is based on these scenarios:

  • If the tree is empty, create a new leaf node and insert your value.
  • If the tree is not empty, traverse through the tree to find the right leaf node where the value should be inserted.
  • If the leaf node has only one value, insert your value into the node.
  • If the leaf node has more than two values, split the node by moving the middle element to the top node.
  • Keep forming new nodes wherever you get more than two elements.

Example - 1

Take a look at the following example where you will build a 2-3 tree from scratch by inserting elements one by one.

Level up your interview prep. Join Educative to access 80+ hands-on prep courses.