Trie Node Structure

Code:

            class TrieNode {
                constructor() {
                    this.children = {};
                    this.isEndOfWord = false;
                }
            }
        

Trie Structure

Code:

            class Trie {
                constructor() {
                    this.root = new TrieNode();
                }
            }
        

Points to Remember

• The root node is the starting point of a Trie data structure.
• Each Trie node has two main properties: children and an end-of-word flag.
• A Trie requires only a root node, and all words and operations originate from it.

Trie Operations

Insert, Search, Prefix

ant, and, cat, cap, car, card

Insert:

• Search(cat): It checks the path and verifies the end-of-word flag, then returns true.
• Search(cal): It returns false when both the path and the end-of-word flag are missing.
• Search(ca): It checks the path; if the path exists but the end-of-word flag does not, it returns false.

• Prefix(cat): True
• Prefix(ca): True

In prefix search, the end-of-word flag is not checked, which is why it returns true in both cases.

Delete Operation

This operation also exists in the Trie data structure but it is generally not used in practice. When a Trie contains billions of words, delete operations become inefficient and difficult to manage.