Word:

Presets:

Overview & Concept

A Trie (Prefix Tree) is an ordered tree data structure used to store an associative array where keys are sequences (usually strings). Unlike a binary search tree, no node in the tree stores the key associated with that node; instead, its position in the tree defines the key with which it is associated. All descendants of a node share a common string prefix, enabling sub-millisecond retrieval, prefix searching, and predictive autocompletion.

How It Works

Shared Prefixes: Strings sharing common prefixes traverse identical branches starting from the ROOT node.

Character Transitions: Each directed edge corresponds to an individual character in the key.

End of Word Flag: Nodes contain an isEndOfWord boolean flag distinguishing complete dictionary words from intermediate sub-prefixes.

Subtree Discovery: All completions of a given prefix string reside in the subtree rooted at that prefix node.

Step-by-Step Execution

1. Root InitializationBegin traversal from the empty string ROOT node.

2. Character TraversalFor each character in the word, follow the corresponding child edge or allocate a new child node if absent.

3. Terminal Flag SettingAt the final character node, set isEndOfWord = true to mark word completion.

4. Prefix Query / PruningFor prefix search: traverse prefix and collect subtree words. For delete: unmark flag and prune leaf branches bottom-up.

Asymptotic Complexity Analysis

Metric	Best Case	Average Case	Worst Case	Space Complexity
Complexity Bound	O(L)	O(L) where L = word length	O(L) guaranteed	O(ALPHABET_SIZE * L * N)
Explanation	Optimal input arrangement minimizing operations.	Expected time for uniformly distributed randomized inputs.	Adversarial degenerate conditions requiring full traversal.	Auxiliary memory allocated beyond original input size.

Pseudocode & Invariants

Algorithm Logic

// Trie (Prefix Tree)
operation insert(word):
  curr = root
  for char in word:
    if not curr.children[char]:
      curr.children[char] = new TrieNode(char)
    curr = curr.children[char]
  curr.isEndOfWord = true

operation search(word):
  curr = root
  for char in word:
    if not curr.children[char]: return false
    curr = curr.children[char]
  return curr.isEndOfWord

operation startsWith(prefix):
  curr = root
  for char in prefix:
    if not curr.children[char]: return false
    curr = curr.children[char]
  return true

Algorithmic Invariants

Prefix Equivalence Invariant: Two keys share identical ancestor nodes if and only if they share that common character prefix.
Depth Invariant: The depth of any node is strictly equal to the length of the prefix it represents.

Correctness Guarantee: Invariants hold true prior to loop entry, are preserved during every iteration, and guarantee correct post-condition upon termination.

Advantages & Disadvantages

Key Advantages

•Ultra-fast O(L) search, insert, and delete where L is key length, completely independent of dictionary size.
•Instant prefix autocompletion and wildcard matching.
•Zero hash collisions compared to hash tables.

Trade-offs & Limitations

•High pointer memory footprint when storing sparse vocabulary without prefix overlap.
•Restricted to sequential string or discrete symbol key types.

Real-World Applications

Search Engine Autocomplete

Suggesting candidate query completions in sub-millisecond windows.

IP Routing Longest Prefix Match (LPM)

Hardware routers resolving destination IP subnets to network interfaces.

Spell Checkers & Predictive Text

Identifying invalid words and suggesting close vocabulary branches.

Decision Guide: When to Use

Ideal Scenarios

✓When building search suggestions, autocomplete, or spell checking.
✓When prefix filtering operations (startsWith) are frequently executed.

Consider Alternatives When

✕When keys have zero common prefixes or are large arbitrary binary objects.

Compare trade-offs and complexity across complementary tools in AlgoViz.

Hash Table Binary Search