prefix tree (trie)

A prefix tree, or trie, is a data structure used to organize words or sequences in a way that makes searching efficient. Imagine a branching diagram where each node represents a letter, and paths from the root form words. If two words share a beginning, they share the same initial branches, branching out only when they differ. This structure allows quick lookups, such as checking if a word exists or finding all words with a common prefix, by following the relevant branches. Tries are especially useful in applications like autocomplete, spell checking, and dictionary storage.