Trie (Prefix Tree)
Set StructuresMediumInsert, delete, and trace string prefixes dynamically in char trees.
Alt+Shift+R
Configuration Panel
Trie Visual Character Forest
Double-click empty canvas to create root, select node to add child or delete.
Trie Word Dictionary:
"cat"
"car"
"dog"
"dot"
Time Complexity
O(L) where L is length of word
Auxiliary Space Complexity
O(N * Σ) alphabet size Σ
Conceptual Overview
A Trie (Prefix Tree) is an ordered tree data structure used to store a dynamic set of keys or strings, where keys are usually strings. Unlike a BST, no node in the tree stores the key associated with that node; instead, its position in the tree defines the key/prefix it is associated with.
Algorithm Mechanism
Starts from an empty root. For each character in a word, inserts children transitions if not present. Ends of words are marked with a terminal flag.
Source: CP-Algorithms reference guide