Trie

About

A General Tree specifically used for efficient retrieval of strings, commonly used in autocomplete features.

Each node can have any number of children.

Searching an element

Inserting an element

1. Starting a the root of Trie.

2. Grab one character of the string being added. (From left to right, in most Languages)

3. Check if the current node has this character.

   1. If it doesn't add the new node with this character.

4. Set the current node to this node and Repeat 2.

5. The last node which refers to the last character of the word being added, can have a flag like isWord to inform that this node completes a word on the Trie.

Deleting an element

1. Recursevely walk the Tree until the end of the deleted string.

2. Delete the nodes on the Post Section of the Recursion, that have only one child.

In some scenarios no nodes will be deleted only the isWord will be set to false.