Hands-On Data Structures and Algorithms with Python - Second Edition

Ternary search tree

A ternary tree is a data structure where each node of the tree can contain up to 3 children. It is different compared to the binary search tree in the sense that a node in a binary tree can have a maximum of 2 children, whereas a node in the ternary tree can have a maximum of 3 children. The ternary tree data structure is also considered a special case of the trie data structure. In trie data structure, each node contains 26 pointers to its children when we use trie data structure to store strings in contrast to the ternary search tree data structure, where we have 3 pointers to its children.

The ternary search tree can be represented as follows:

• Each node stores a character in it
• It has the equal pointer that points ...