Trie Data Structure Implementation

What is a Trie?

A "Trie", also known as a "Prefix Tree", is a tree data structure where the nodes store letters inside of the alphabet. Using this data structure, you can traverse branches of the tree to search for words or prefixes. You can also search for suffixes depending on how the data is inserted inside of the Trie.

Where are Tries used?

Tries are most commonly used in autocompletion algorithms. If you are typing into your phone and start seeing word recommendations, under the hood the recommended words are prefixes to what you have typed thus far. Another similar use case where Tries are used in the real world is for spell checking. If you type in a word incorrectly, the Trie data structure can recommend previously validated words to use instead.

What are the common methods in a Trie?

The most common methods that are implemented in a Trie are insert, search, and startsWith. The insert method, exactly how it sounds, will add a group of characters into the Trie data structure sequentially. The search method will look to see if a specific word exists in the Prefix Tree or not. Finally, the startsWith method will look to see if a specific prefix exists in the Prefix Tree or not.

Video Explanation of Implement Trie (Prefix Tree) LeetCode Question # 208

This Youtube video goes over LeetCode question # 208 for implementing the Trie data structure. You will learn how to implement the insert, search, and startsWith methods along with what each method's time and space complexity is.

Since we only have to worry about words containing lowercase letters, we can create an array of nodes of size 26 where each index will be responsible for storing an individual lowercase letter. To implement insertion, we will have node called 'curr' which starts at our root node. We move this 'curr' node down the branches of our tree creating nodes along the way for each character in our word. Our search and startsWith functions will have very similar logic where we move down the branches and return the last character in the word we are looking for.

The time complexity for all 3 functions will be O(M) where M is the number of characters we have in our word. We must traverse M nodes in the worst case when performing these functions. The space complexity of insert will be O(M) because we must create M nodes per insert. Finally, our space complexity of search and startsWith will be O(1) constant space since we do not initialize extra memory in those functions.

Quick Answers

What is another term for Trie?

Another term for a Trie is a Prefix Tree.

Where is a Trie used?

A Trie is commonly used in autocompletion and spellchecking algorithms.

What is the time complexity for inserting in a Trie?

The time complexity for insertion in a Trie is linear time, specifically O(N) where N is the number of characters there are in the word we are inserting.

What is the space complexity for inserting in a Trie?

The space complexity for insertion in a Trie is linear, O(N) where N is the number of characters there are in the word we are inserting. In the worst case, we are creating N new nodes in our Trie per insert.

What is the time complexity for searching in a Trie?

The time complexity for searching in a Trie is linear time, specifically O(N) where N is the number of characters there are in the word we are searching for.

What is the space complexity for searching in a Trie?

The space complexity for searching in a Trie is constant, O(1) because no new nodes need to be created when searching.