- also known as *prefix tree* - stores characters of a string at each node ![[CleanShot 2024-08-14 at [email protected]]] - can be used to efficiently implement string searching/matching algorithms - keeps track of which words have the characters as prefix ``` # note: using a class is only necessary if you want to store data at each node. # otherwise, you can implement a trie using only hash maps. class TrieNode: def __init__(self): # you can store data at nodes if you wish self.data = None self.children = {} def build_trie(words): root = TrieNode() for word in words: curr = root for c in word: if c not in curr.children: curr.children[c] = TrieNode() curr = curr.children[c] # at this point, you have a full word at curr # you can perform more logic here to give curr an attribute if you want return root ``` ![[Pasted image 20240814161230.png]] - think about edges as the [[Hashmaps|Dictionary]] keys, and the TrieNode nodes as the [[Hashmaps|Dictionary]] values