- 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