# Compressed Trie

A Compressed Trie compress the paths of nodes with only one child.

- Each node stores an index, corresponding to the depth in the uncompressed trie
- This gives the next bit to be tested during a search

- A compressed trie with $n$ keys has at most $n−1$ internal nodes