# What Is M-Way Search Tree in Data Structure?

//

Scott Campbell

A M-Way search tree, also known as an M-ary search tree, is a data structure that is used to store and organize a collection of data in a hierarchical manner. It is similar to a binary search tree, but instead of having two children for each node, an M-Way search tree can have up to M children for each node.

## Structure

In an M-Way search tree, each node can have up to M children. The nodes are arranged in such a way that the values stored in the left subtree are less than the value at the current node, and the values stored in the right subtree are greater than the value at the current node.

Let’s take an example to understand this better. Consider an M-Way search tree with M = 3:

8
/ | \
3  10  14
/ \    / \
1   6 11   16

In this example, each node can have up to three children. The value at the root node is 8, and its left subtree contains values less than 8 (3 and 1), while its right subtree contains values greater than 8 (10 and 14).

## Searching

Searching in an M-Way search tree follows a similar approach to searching in a binary search tree. Starting from the root node, we compare the value we are searching for with the value at the current node.

If they are equal, we have found our desired value. If it is less than the current node’s value, we move to its left child; otherwise, we move to its right child.

The process continues until we find our desired value or reach a leaf node (a node with no children). If we reach a leaf node and still haven’t found the value, it means that the value is not present in the tree.

## Operations

Some common operations performed on M-Way search trees include:

• Insertion: To insert a new value into an M-Way search tree, we follow the same approach as searching. We traverse the tree until we find a suitable leaf node to insert the new value as a child.

If there is no space for a new child, we may need to split the node and rearrange the tree structure to accommodate the new value.

• Deletion: Deleting a value from an M-Way search tree involves finding the node containing the value and removing it from the tree. If removing a node leaves other nodes with fewer than M-1 children, we may need to perform some restructuring to maintain the properties of an M-Way search tree.
• Traversal: Traversing an M-Way search tree can be done using various algorithms such as inorder traversal, preorder traversal, or postorder traversal. These algorithms visit each node in a specific order, allowing us to process or display the values stored in the tree.