# What Is Ternary Tree in Data Structure?

//

Scott Campbell

A ternary tree, also known as a 3-ary tree or a tri-nary tree, is a type of tree data structure where each node can have at most three children. It is an extension of the binary tree, which allows each node to have at most two children.

## Structure of a Ternary Tree

In a ternary tree, each node can have up to three child nodes. The children are typically referred to as the left child, middle child, and right child. The left child represents values less than the current node’s value, the middle child represents values equal to the current node’s value, and the right child represents values greater than the current node’s value.

The structure of a ternary tree can be visualized as follows:

```            X
/ | \
/  |  \
/   |   \
Left    Middle Right
```

## Applications of Ternary Trees

Ternary trees are commonly used in various applications such as:

• Dictionary data structures: Ternary trees can be used for efficient storing and retrieval of key-value pairs.
• Spellcheckers: Ternary trees can be used to store and search for words in a dictionary efficiently.
• T9 predictive text: Ternary trees can be utilized in mobile phone keyboards for implementing predictive text functionality.

## Operations on Ternary Trees

Similar to other types of trees, ternary trees support various operations such as:

• Insertion: To insert a new element into a ternary tree, we compare it with the current node’s value. If it is less than the current node, we move to the left child. If it is equal to the current node, we move to the middle child. If it is greater than the current node, we move to the right child. We repeat this process until we find an appropriate position for insertion.
• Deletion: To delete a node from a ternary tree, we first search for the node to be deleted.

Once found, we handle different cases depending on whether the node has children or not.

• Search: To search for a particular element in a ternary tree, we compare it with each node’s value starting from the root. If the element is less than the current node’s value, we move to its left child. If it is equal to the current node’s value, we move to its middle child. If it is greater than the current node’s value, we move to its right child. We repeat this process until we find a matching element or reach a null pointer.