2-3 Insertion

This lesson will explain how insertion is done in 2-3 Trees based on multiple scenarios that are explained with the insertion algorithm.

Introduction

Insertion in 2-3 Trees is a lot different from the insertion in Binary Search Trees. In 2-3 Trees, values are only inserted at leaf nodes at certain conditions. As discussed before, the insertion algorithm takes O(log n)O(log\ n) 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. So overall the time complexity of the insertion algorithm is O(log n)O(log\ n). Let’s see how it works.

Insertion Algorithm

The insertion algorithm is based on these scenarios:

  • Initially 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

Let’s take a look at the following example where we will build a 2-3 Tree from scratch by inserting elements one by one.

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