A 2-3 Tree is a specific form of a B tree. A 2-3 tree is a search tree. However, it is very different from a binary search tree.

2-3 tree is a tree data structure in which every internal node (non-leaf node) has either one data element and two children or two data elements and three children. If a node contains one data element **leftVal**, it has two subtrees (children) namely **left **and **middle**. Whereas if a node contains two data elements **leftVal **and **rightVal**, it has three subtrees namely **left**, **middle **and **right**.

The main advantage with 2-3 trees is that it is balanced in nature as opposed to a binary search tree whose height in the worst case can be O(n). Due to this, the worst case time-complexity of operations such as search, insertion and deletion is O(Log(n)) as the height of a 2-3 tree is O(Log(n)).

## Properties of a 2-3 Tree:

- a node with one value is either a leaf node or has exactly two children (non-null). Values in left subtree < value in node < values in right subtree
- a node with two values is either a leaf node or has exactly three children (non-null). Values in left subtree < first value in node < values in middle subtree < second value in node < value in right subtree.
- all leaf nodes are at the same level of the tree

### Insertion

The insertion algorithm into a two-three tree is quite different from the insertion algorithm into a binary search tree. In a two-three tree, the algorithm will be as follows:

- If the tree is empty, create a node and put value into the node
- Otherwise find the leaf node where the value belongs.
- If the leaf node has only one value, put the new value into the node
- If the leaf node has more than two values, split the node and promote the median of the three values to parent.
- If the parent then has three values, continue to split and promote, forming a new root node if necessary

**Example:**

** **Insert **50**

** **

** **Insert **30**

** **

Insert **10**

Insert **70 **and **60**

### Deleting node from 2-3 Tree

** **

**Final Tree**