For the use case of searching strings, the time complexity of a binary search tree could be O(n) in the worst case. Where ‘n’ is the total number of strings stored in the binary tree. Therefore a better performing data structure is needed for searching strings in optimal time. The trie data structure avoids traversing the whole tree while searching for a string. A string containing only letters limits a trie node’s children to 26. This allows the search time complexity of a string to be O(s) where ‘s’ is the length of the string. So a trie tree is much more efficient in searching strings compared to the binary search tree.
The structure for a single node in the trie tree consists of an array of size 26 and a boolean to identify if it is the leaf node. Additionally, the leaf node can have an integer value or any other type of value mapped to the string. Each index in the array represents letters from a to z and each index can have a ‘TrieNode’ instance.
This image represents the root node in a trie tree.
The properties for ‘TrieNode’ class are ‘value’, ‘isEnd’ and ‘arr’. The ‘arr’ variable is an array of size 26 filled with null values.
The ‘TrieTree’ class has ‘insert’, ‘searchNode’, ‘startsWith’, ‘printString’ and ‘getRoot’ methods. Where the ‘insert’ method takes in a string and value as arguments. A prefix search can be performed with the ‘startsWith’ method.
The code below shows how ‘TrieTree’ class can be instantiated and demonstrates the usage of various methods.
The time and space complexities for different methods are as follows:
- searchNode: Time: O(s), 's' is the string length, Space: O(1), as no extra data structures like queue or stack are used.
- insert: Time: O(s), 's' is the string length, Space: O(ns), where 'n' is the number of keys in the trie tree and 's' is the string length.
- startsWith: Time: O(s + k), 's' is the string length and 'k' is the largest length of the remaining matched string, Space: O(k), where 'k' is the largest length of the remaining matched string.
In front-end development trie trees have applications in the following domains:
- Autocomplete and type ahead functionalities.
- Spell checking.
Additionally, a trie tree can help to store people’s phone numbers, IP addresses, and objects.
💡 Practice Coding
Practice coding questions that involve the trie tree and other data structures from top companies like Google, Amazon, Apple, and others. Signup today at Softnami's daily coding.