A Trie (pronounced "try") is a tree data structure that is used to store Strings. It's generally used to search and store by prefix, which is why it is also known as a "prefix tree."
Tries can often come up in software engineering interviews, however they aren't generally taught in a typical Data Structures course. Like all data structures, they're often better understood by interacting with them.
This guide was made by @FlaqueEau to help out members of the Gonzaga University Makers and Developers club and the greater dev community. If you find something wrong or want to add more, we'd love to merge your pull request!
The insert method of a Trie works by taking string and progressively taking each letter. The first node is generally empty, but for the purposes of explaination, we've labeled it as
"root" in the demo below.
def insert(word): # Step 1: Grab the first letter of the word. firstLetter = word # Step 2: Check if this letter already exists in # our children at this node. if not this.children[firstLetter]: this.children[firstLetter] = new Trie() # Step 3: Pop off the first letter, then recurse. word = word.removeFirstLetter() this.children[firstLetter].insert(word)
The find method of a Trie works in the same way that most other tree structures work. Take the first letter of the word you're looking for and see if that exists as a child node. If it doesn't, you can stop, as that word does not exist in the Trie. Otherwise, find the node with that letter and search it's children for the next lettter. If you've run out of letters, then you've your item.
def find(word): # Step 1: Do a check to see we've found the node if isEmptyString(word) return true; # Step 2: Check to see if we've hit a letter that's not # in the children of the current node const firstLetter = word; if not this.children[firstLetter]: return false; else: # Step 3: Pop off the first letter and continue searching word = word.removeFirstLetter() return this.children[firstLetter].find(word)