Implementing a Trie

Tries

A trie data structure is utilized for searching or retrieving data. The most critical and frequent operations involved in a trie data structure are:

• Insertion of a word.

• Searching for a word/prefix.

Implementing tries

Let's begin implementing a trie class with given functions.

• Trie(): This initializes the trie object.

• void insert (String word): This inserts the string word into the trie.

• boolean search (String word): This returns true if the string word exists in the trie (i.e., it was inserted earlier) and false otherwise.

• boolean startsWith (String pref): This returns true if a previously inserted string word contains pref as a prefix; it returns false otherwise.

Trie node

Every node of the trie can have multiple children. Each child represents a possible character of the key/string. A popular way is to mark the last node of every key/string as the end of the word node.

A trie node field isEndOfWord distinguishes the node as the end of the word node. A simple structure to represent nodes of the English alphabet is as follows.