Trie

A trie is a tree where each node is associated with a letter in an alphabet and a bit for whether the letters along the path from the root to the node form a word in a dictionary.

It’s easiest to imagine a trie with every word in a dictionary in it:

		   	root
		 /   |   |  \
	   a     b   c  ...
    /  |  \
	a  b*  ...

b* has the asterisk, because root \(\rightarrow\) a \(\rightarrow\) b forms the word “ab”. The nodes associated with words may also get some value or payload and the search function can return this value. Or the search function can just return whether the word exists.

Going to the next level in the tree is going to the next position in a word, e.g. the 3rd level is all the 3 letter words.

class TrieNode:
    def __init__(self, value=None):
        # If value is not None, then it both carries the payload
        # for a word and signifies that we've reached the end of a word.
        self.value = value
        self.children = {}

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def search(self, word):
        node = self.root
        for ch in word:
            if ch in node.children:
                node = node.children[ch]
            else:
                return None
        return node.value

    def insert(self, word, value):
        node = self.root
        for ch in word:
            if ch not in node.children:
                node.children[ch] = TrieNode()
            node = node.children[ch]
        node.value = value