# 2-3 Trees

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.

Here are the properties of a 2-3 tree:

1. each node has either one value or two value
2. 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
3. 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.
4. all leaf nodes are at the same level of the tree

### Insertion <a href="#insertion" id="insertion"></a>

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:

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

#### Example: <a href="#example" id="example"></a>

Insert 50

![](https://cathyatseneca.gitbooks.io/data-structures-and-algorithms/content/assets/twothree1.png)

Insert 30

![](https://cathyatseneca.gitbooks.io/data-structures-and-algorithms/content/assets/twothree2.png)

Insert 10

![](https://cathyatseneca.gitbooks.io/data-structures-and-algorithms/content/assets/twothree3.png)

Insert 70&#x20;

![](https://cathyatseneca.gitbooks.io/data-structures-and-algorithms/content/assets/twothree4.png)

Insert 60&#x20;

![](https://cathyatseneca.gitbooks.io/data-structures-and-algorithms/content/assets/twothree5.png)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://catherine-leung.gitbook.io/data-strutures-and-algorithms/2-3-trees.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.