Trie Data Structure: Overview and Practice Problems

Trie Data Structure

Trie is a tree-based data structure, used for efficient retrieval of a key in a large data-set of strings. Unlike a binary search tree, where the node in the tree stores the key associated with that node, the Trie node’s position in a tree defines the key with which it is associated, and the key is only associated with the leaves. It is also known as prefix tree as all descendants of a node have a common prefix of the string associated with that node, and the root is associated with the empty string.

Following are the list of commonly asked Trie interview questions:

1. Trie Implementation — C, C++, C++ (Memory Efficient), Java, Python
2. Longest Common Prefix in a given set of strings (using Trie)
3. Lexicographic sorting of a given set of keys
4. Find the maximum occurring word in a given set of strings
5. Find first `k` maximum occurring words in a given set of strings
6. Find duplicate rows in a binary matrix
7. Word Break Problem — Using Trie Data Structure
8. Generate a list of possible words from a character matrix
9. Find all words matching a pattern in the given dictionary
10. Find the shortest unique prefix for every word in an array

Thanks for reading.