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.
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
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