Trie is also known as digital tree or prefix tree, it is a type of search tree.
It's a tree data structure generally used to store strings, where each node stores individual
character and links to next characters
Each node stores a character, a flag of doesItCompleteAWord and an array or HashTable of all of its children nodes
Trie is also known as digital tree or prefix tree, it is a type of search tree. It's a tree data structure generally used to store strings, where each node stores individual character and links to next characters
Each node stores a character, a flag of doesItCompleteAWord and an array or HashTable of all of its children nodes
e.g. "car" => {"*", root} --> {'c', completesWord: false} --> {'a', completesWord: false} --> {'r', completesWord: True}
Basically nodes are linked not by entire keys, but by individual characters
Files: Trie | Test