# What Is a 2/4 Tree in Data Structure?

//

Heather Bennett

A 2/4 tree, also known as a two-four tree or a 2-3-4 tree, is a self-balancing search tree data structure that allows efficient insertion, deletion, and retrieval operations. It is an extension of the binary search tree (BST) where each node can have up to four children. In this article, we will explore the characteristics and operations of a 2/4 tree.

## Structure of a 2/4 Tree

A 2/4 tree consists of nodes that can be of three types:

• A 2-node has one key and two children.
• A 3-node has two keys and three children.
• A 4-node has three keys and four children.

The keys in each node are arranged in sorted order. For example, in a 3-node, the left key is smaller than the middle key, and the middle key is smaller than the right key. The children between these keys are arranged accordingly.

### Insertion Operation

To insert a new key into a 2/4 tree:

1. If the root is null, create a new root node with the new key as its only element.
2. If the root is not null, traverse down the tree to find the appropriate leaf node to insert into.
• If the leaf node is a 2-node, convert it into a 3-node by adding the new key to it. The resulting node becomes a temporary 4-node.
• If the leaf node is already a temporary 4-node (due to a previous insertion), split it into two 2-nodes by promoting the middle key to its parent node.
• If the parent node is also a temporary 4-node, repeat the process until a suitable parent can accept the new key.

### Deletion Operation

To delete a key from a 2/4 tree:

1. If the key is present in an internal node, replace it with its predecessor or successor key and delete the predecessor/successor from its original position in a leaf node.
2. If the key to be deleted is in a leaf node, simply remove it.
• If removing the key results in an underflow (less than two keys) in any non-root node, perform balancing operations such as borrowing keys from siblings or merging nodes.
• If an underflow occurs at the root and only one child is left, make that child the new root.