Trie data structure - Interactive Learning
Master Trie (Prefix Tree) - DSA Learning Platform 🌳 Master Trie (Prefix Tree) String Storage O(m) Operations Learn Trie operations with insertion, search, autocomplete, and prefix matching 📖 Understanding Trie Introduction Structure Operations Applications Complexity What is a Trie? A Trie (pronounced "try"), also called a Prefix Tree or Digital Tree, is a tree-like data structure used to efficiently store and retrieve strings. Unlike binary trees, each node can have multiple children (up to the size of the alphabet). The name "Trie" comes from the word "retrieval" because it's optimized for retrieving strings from a dictionary. Each path from root to a node represents a prefix of the stored strings. Tries are especially useful when you need to search for words with common prefixes, making them ideal for autocomplete systems, spell checkers, and IP routing tables. 🔑 Key Properties Each node represents a character Root is empty (represents ""); Path from root forms a prefix Nodes can be marked as "end of word" Common prefixes share same path Operations depend on word length, not tree size Trie Structure Each node in a Trie contains: Children: Map/Array of child nodes (one per character) isEndOfWord: Boolean flag marking word completion Optional: Character stored, word count, etc. For an English lowercase alphabet, each node can have up to 26 children (a-z). The space can be optimized using a HashMap instead of a fixed-size array. Example: Storing "cat", "car", "card" shares the path for "ca" 📍 Trie Structure Example Words: "cat", "car", "card", "dog" (root) / \ c d | | a o / \ | t r g* * * \ d* * = End of Word marker Trie Operations 📥 Insert Word Start from root For each character in word: If child doesn't exist, create it Move to the child node Mark final node as end of word 🔍 Search Word Start from root For each character in word: If child doesn't exist → Not found Move to the child node Return true if isEndOfWord is true 🔤 Search Prefix Same as search but don't check isEndOfWord Returns true if path exists ⏱️ Time Complexity Insert: O(m) - m = word length Search: O(m) Delete: O(m) Prefix Search: O(m) Autocomplete: O(m + k) - k = matches 💾 Space Complexity Worst: O(ALPHABET_SIZE × m × n) n = number of words Can be optimized with HashMap Real-World Applications 🔍 Autocomplete Search engines, IDEs, and text editors use tries for real-time suggestions as you type. 📖 Spell Checker Dictionary lookups and spelling corrections use tries for fast word validation. 🌐 IP Routing Network routers use tries (Radix trees) for longest prefix matching in routing tables. 📱 T9 Predictive Text Old mobile phone keyboards used tries for predictive text input. 💡 More Applications Word games (Scrabble, Boggle) DNA sequence matching Phone directory Browser history Command-line tab completion Contact list search 🎯 When to Use Trie Need prefix-based operations Many strings share prefixes Fast lookup is critical Autocomplete functionality Trie vs Other Data S...
Subject: Data Structures with Animation | Chapter: Trie Data Structure