Trie (Prefix Tree)
Visualize string insertion, exact matching, and prefix search operations within a Trie data structure.
Free theory articleVisualize string insertion, exact matching, and prefix search operations within a Trie data structure.
Concept & interpretation
A Trie (pronounced "try" or "tree"), also known as a digital tree or prefix tree, is a type of search tree used to store a dynamic set of sequences, typically strings. Unlike a binary search tree, where nodes store keys and are compared to determine traversal paths, in a Trie, the position of a node in the tree determines the key it is associated with. All descendants of a node share a common prefix of the string associated with that node. This structural property makes Tries exceptionally efficient for prefix-matching and autocomplete operations.