Suggest an editImprove this articleRefine the answer for “What is a trie (prefix tree)?”. Your changes go to moderation before they’re published.Approval requiredContentWhat you’re changing🇺🇸EN🇺🇦UAPreviewTitle (EN)Short answer (EN)**A trie (prefix tree)** is a data structure that stores strings character by character, allowing efficient prefix search. **Key point:** a trie allows fast word lookup and prefix-based autocomplete, storing large dictionaries without duplicating shared prefixes.Shown above the full answer for quick recall.Answer (EN)Image**A trie (prefix tree)** is a data structure that stores strings character by character, allowing efficient prefix search. Each **tree node** represents a single character, and the path from the root to a node is the **prefix** of some string. A complete word ends at a node marked as the *end of word*. **Example:** For the words `cat`, `car`, `dog` the tree looks like this: - Root → `c` → `a` → `t` (end of word) ↳ `r` (end of word) - Root → `d` → `o` → `g` (end of word) **Main operations:** - **Insertion:** O(L), where L is the length of the word. - **Search:** O(L). - **Prefix search:** O(P), where P is the length of the prefix. **Advantages:** - Fast word lookup and prefix-based autocomplete. - Large dictionaries can be stored without duplicating shared prefixes. **Disadvantages:** - Uses more memory than a hash table (many child pointers).For the reviewerNote to the moderator (optional)Visible only to the moderator. Helps review go faster.