A **2-3-4 Tree** is a multiway search tree. It's a *self-balancing* tree; it’s always perfectly balanced with every leaf node at equal distance from the root node.

Other than the leaf node, every node can be one of three types:

 * **2-Node** has two child nodes and one data element

 * **3-Node** has three child nodes and two data elements

 * **4-Node** has four child nodes and three data elements 

# Structure of a 2-Node

Like a binary search tree, when a node only contains one data element the left subtree of that node (parent node) will contain nodes with data elements valued less than the parent node's data elements, while the right subtree will contain nodes with data elements valued greater than the parent node's data elements. Nodes having the same value as their parent node can be inserted in either the left or the right subtree.



### Structure of a 3-Node

When a node contains two data elements, the left data element is less than the right data element.  

The leftmost subtree of a node containing two data elements, we will call the parent node, will contain nodes with data elements less than the parent node's lesser valued data element.

The rightmost subtree of the parent node will contain nodes with data elements greater than the parent node's greater valued data element.

As a node with two data elements can have three child nodes, the middle subtree of the parent node will have nodes with data elements greater than the lesser element of the parent node, but lesser than the greater element of the parent node.

# Structure of a 4-Node

When a node contains three data elements, the values of those data elements are sorted from least to greatest (left to right). The structure of a 4-Node is similar to that of a 3-Node with the addition of an extra data element hence, resulting in the possibility of 4 subtrees. 


# Insertion
When inserting a new data element in a **2-3-4 Tree**, always remember that new elements are inserted only in leaf nodes. 

**Simple Insertion:** After the appropriate leaf node is located, we must check the number of data elements it contains. If the leaf node contains less than 3 data elements, we will do a simple insertion.

**Insertion with Preemptive Splitting:** If the leaf node already has the maximum number of data elements i.e. 3 (**4-Node**), it needs to be split before insertion. To split a **4-Node**. follow the steps below:
1. Pick the middle element and move it to the parent. If it's the root and has no parent, a new root is created, and the middle element moves to the new root.

2. Create two **2-Nodes** and move the left element to one node (we will call it left **2-Node**) and the right element to the other (we will call this one right **2-Node**).

3. If the original **4-Node** had children, they would now become the children of the newly created **2-Nodes** 

# Time Complexity
The property of being perfectly balanced enables the **2-3-4 Tree** operations of insert, delete and search to have time complexities of $O(log (n))$.

What is a 2-3-4 Tree?

Structure of a 2-Node

Structure of a 3-Node

Structure of a 4-Node

Insertion

Time Complexity