Login
C Tutorials C++ Tutorials Java Tutorials Python Tutorials JavaScript Tutorials TypeScript Tutorials C# Tutorials Go Tutorials Rust Tutorials PHP Tutorials Kotlin Tutorials Swift Tutorials
HTML Tutorials CSS Tutorials Frontend Development Backend Development React Tutorials Next.js Tutorials Node.js Tutorials Django Tutorials Mobile App Development
Beginner Tutorials Advanced Guides Coding Roadmaps Interview Preparation DSA Tutorials Projects & Examples Cheat Sheets
About Us Contact Privacy Policy Terms & Conditions Disclaimer Sitemap

Tries (Prefix Trees): Efficient String Storage and Retrieval

A Trie (pronounced 'try', derived from re**trie**val), also known as a Prefix Tree, is a specialized tree-like data structure used to store and retrieve strings efficiently over an alphabet. Unlike binary search trees or hash tables, keys are not stored directly within individual nodes; instead, a node's position in the tree defines the key associated with it.

All descendants of a particular node share a common string prefix. This structural property makes Tries the foundation for autocomplete systems, spell checkers, dictionary validations, and IP routing tables.

Anatomy of a Trie Node

A typical Trie node contains two core components:

  • Children References: An array or hash map mapping alphabet characters to child node pointers (e.g., an array of size 26 for lowercase English letters 'a' through 'z').
  • Terminal Flag (isEndOfWord): A boolean marker indicating whether the path from the root to this specific node constitutes a complete, valid word or just an intermediate prefix.

Core Operations and Complexity Analysis

1. Insertion

Starting at the root, iterate through each character of the string. If a child pointer for the current character does not exist, instantiate a new Trie node. Advance down the path and mark the final character's node with `isEndOfWord = true`. Time Complexity: O(L), where L is the length of the string.

2. Exact Search

Traverse the tree character by character. If a character branch is missing at any level, the word does not exist in the Trie. If traversal completes, return the value of `isEndOfWord` (ensuring the prefix is indeed a standalone word). Time Complexity: O(L).

3. Prefix Search (startsWith)

Follow the path corresponding to the query prefix. If all characters in the prefix are traversed successfully, return true regardless of whether the final node's `isEndOfWord` flag is set. Time Complexity: O(P), where P is prefix length.

4. Deletion

Remove a word using a post-order traversal: uncheck `isEndOfWord` at the target node, and recursively prune child nodes upward if they have no other active children and do not mark the end of another valid word.

Trie vs. Hash Table: Trade-Offs

While Hash Tables provide average O(1) lookups, Tries offer key structural advantages in specific domains:

  • Prefix Operations: Tries find all keys sharing a common prefix in O(P + K) time, whereas Hash Tables require scanning all stored keys in O(N).
  • No Hash Collisions: Worst-case lookup in a Trie is strictly bounded by string length O(L), with no degradation from hash collisions.
  • Lexicographical Ordering: Tries naturally maintain keys in alphabetical order, making sorted traversals straightforward.
  • Memory Trade-Off: Standard Tries consume significant memory due to sparse pointer arrays in non-dense alphabets.

Real-World Applications

  1. Search Engine Autocomplete & Typeahead: Traversing to a prefix node and performing Depth-First Search (DFS) or Breadth-First Search (BFS) to gather top-ranked suggestions.
  2. Network IP Routing (Longest Prefix Match): Storing CIDR routing tables in binary Tries to quickly determine packet forwarding hops.
  3. Spell Checkers & Lexicons: Validating dictionary words and suggesting nearest edit-distance corrections via Levenshtein-Trie traversals.
  4. Compressed Variants (Radix Tree / Patricia Trie): Merging single-child nodes to drastically compress memory footprint in production databases and key-value stores.