trie = a data structure used to store large sets of strings

while storing in an array etc. is ok (O(n) lookup), we can use a trie to improve to O(L) where L is the length of the string

each word is essentially stored as a linked-list of letters, where we mark where each word terminates (e.g. allows us to store both ‘app’ and ‘apple’)

each node in a trie contains:

depth of a trie = length of longest word

major disadvantage of tries: tries take up a lot of space

pointers to children nodes for each letter could be 8 bytes per pointer

each node will need even more children to store characters such as uppercase letters or numeric characters etc.

trie implementation

performance analysis

space complexity = O(n)

n = sum of lengths of all strings

insertion complexity = O(L)

L = length of word to insert

search complexity = O(L)

L = length of word to search

alternatives to normal tries

  1. BST-like tries

    to reduce the space problem that tries face, we can implement them more like BSTs

    each node has two children — down and right

    going down gives the next letter

    going right gives alternate letters

    less space used, maintaining (insert / delete) not really affected

    however, this will take more time to search