String Algo

Trie Prefix Tree

A search tree optimized for prefix matches and dictionary lookups.

What is Trie Prefix Tree?

A Trie (Prefix Tree) is an ordered tree-like data structure used to store strings. Unlike a standard search tree, nodes do not store key values; instead, their position in the tree defines the key. Each node represents a single character, and path traversals from root downward spell out words. This structure is highly optimized for auto-completion, dictionaries, and spellcheckers.

Key Characteristics:

  • Root represents empty string
  • Each path represents character sequence
  • Shared prefixes share common paths in memory
  • End-Of-Word flags mark complete strings

Complexity Analysis

Avg Time Complexity: O(L) for Insert and Search (L = string length)
Space Complexity: O(Alphabet_Size * Nodes_Count * L)
Best Case: O(L) (finding or inserting prefix)
Worst Case: O(L) (navigating full string length)

How it Works Step-by-Step

  1. Insert: For each char, check if child node exists; if not, create child, and mark last as EndOfWord.
  2. Search Word: Follow character nodes down. Return true if last node has EndOfWord flag.
  3. Search Prefix: Follow character nodes down. Return true if path is complete.

Code Implementation

Worked Trace Example

Inserting 'cat' and 'cab' in empty Trie:
1. Insert 'cat': root ➔ 'c' ➔ 'a' ➔ 't' (mark 't' as end)
2. Insert 'cab': shares prefix 'c' and 'a' ➔ branches at 'a' to 'b' (mark 'b' as end)
Result: Trie holds words branching from 'a'.