# 2-3 Insertion

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

We'll cover the following

## Introduction

Insertion in 2-3 Trees is a lot 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)$ time where n is the number of nodes in the tree. Searching for an element is done in $Log(n)$ and then insertion takes a constant amount of time. So, the overall time complexity of the insertion algorithm is $O(Logn)$.

## Insertion Algorithm

The insertion algorithm is based on these scenarios:

• If the tree is initially 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.