What is a Trie (Prefix Tree)?

A Trie (pronounced “try”) is a specialized tree-like data structure used to store strings efficiently, especially for operations like searching, inserting, and deleting prefixes. It is commonly called a prefix tree because it enables fast prefix-based lookups.

Tries are widely used in autocomplete systems, spell checkers, dictionary implementations, and IP routing tables.

---

Why Use a Trie?

1. Fast Search and Insert (O(m)):
   Unlike hash tables (O(1) on average but O(n) in the worst case), a Trie guarantees O(m) time complexity for searching and inserting a word, where m is the length of the word.
2. Efficient Prefix Searches:
   Unlike binary search trees (BSTs), a Trie allows fast prefix-based searches (e.g., finding all words starting with “pre”).
3. Avoids Collisions:
   Unlike hash tables, which can have hash collisions, a Trie ensures deterministic lookups.
4. Memory Trade-off:
   A Trie can consume more memory than hash tables due to pointers for each character, but compressed tries like Radix Trees help optimize space.

---

Structure of a Trie Node

Each Trie node contains:

• Children: A dictionary or array storing child nodes for each character.
• End-of-Word Flag: A boolean indicating if the node is the end of a valid word.

For example, storing “car”, “cat”, and “bat” in a Trie looks like this:

        (root)
       /      \
      c        b
     / \        \
    a   a        a
   /     \        \
  r       t        t

---

Basic Trie Operations

1. Insertion

• Start at the root.
• Traverse down the Trie, adding nodes for missing characters.
• Mark the last node as end-of-word.

2. Search

• Start at the root.
• Traverse through each character in the Trie.
• If all characters exist and end-of-word is marked, return True; otherwise, return False.

3. Prefix Search

• Similar to search, but doesn’t require the last node to be an end-of-word.

4. Deletion

• If the word exists, remove nodes if they are not shared with other words.

---

Python Implementation of a Trie

class TrieNode:
    def __init__(self):
        self.children = {}  # Dictionary to store children nodes
        self.is_end_of_word = False  # Marks if this node is the end of a word

class Trie:
    def __init__(self):
        self.root = TrieNode()  # Initialize Trie with an empty root node

    def insert(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()  # Create a new node if character not found
            node = node.children[char]
        node.is_end_of_word = True  # Mark the last node as end-of-word

    def search(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                return False  # If a character is missing, word does not exist
            node = node.children[char]
        return node.is_end_of_word  # Check if the last node is marked as end-of-word

    def starts_with(self, prefix):
        node = self.root
        for char in prefix:
            if char not in node.children:
                return False
            node = node.children[char]
        return True  # Prefix exists in Trie

    def delete(self, word):
        def _delete(node, word, depth):
            if depth == len(word):
                if not node.is_end_of_word:
                    return False  # Word not found
                node.is_end_of_word = False
                return len(node.children) == 0  # If node has no children, delete it
            
            char = word[depth]
            if char not in node.children:
                return False  # Word not found
            
            should_delete = _delete(node.children[char], word, depth + 1)
            
            if should_delete:
                del node.children[char]
                return len(node.children) == 0  # If no children left, delete node
            
            return False

        _delete(self.root, word, 0)

# Example Usage
trie = Trie()
trie.insert("car")
trie.insert("cat")
trie.insert("bat")

print(trie.search("car"))  # True
print(trie.search("bat"))  # True
print(trie.search("can"))  # False
print(trie.starts_with("ca"))  # True
trie.delete("car")
print(trie.search("car"))  # False

---

Java Implementation of a Trie

import java.util.HashMap;
import java.util.Map;

class TrieNode {
    Map<Character, TrieNode> children = new HashMap<>();
    boolean isEndOfWord = false;
}

class Trie {
    private TrieNode root;

    public Trie() {
        root = new TrieNode();
    }

    public void insert(String word) {
        TrieNode node = root;
        for (char ch : word.toCharArray()) {
            node.children.putIfAbsent(ch, new TrieNode());
            node = node.children.get(ch);
        }
        node.isEndOfWord = true;
    }

    public boolean search(String word) {
        TrieNode node = root;
        for (char ch : word.toCharArray()) {
            if (!node.children.containsKey(ch)) {
                return false;
            }
            node = node.children.get(ch);
        }
        return node.isEndOfWord;
    }

    public boolean startsWith(String prefix) {
        TrieNode node = root;
        for (char ch : prefix.toCharArray()) {
            if (!node.children.containsKey(ch)) {
                return false;
            }
            node = node.children.get(ch);
        }
        return true;
    }

    public void delete(String word) {
        delete(root, word, 0);
    }

    private boolean delete(TrieNode node, String word, int depth) {
        if (depth == word.length()) {
            if (!node.isEndOfWord) {
                return false;
            }
            node.isEndOfWord = false;
            return node.children.isEmpty();
        }

        char ch = word.charAt(depth);
        if (!node.children.containsKey(ch)) {
            return false;
        }

        boolean shouldDelete = delete(node.children.get(ch), word, depth + 1);
        if (shouldDelete) {
            node.children.remove(ch);
            return node.children.isEmpty();
        }
        return false;
    }

    public static void main(String[] args) {
        Trie trie = new Trie();
        trie.insert("car");
        trie.insert("cat");
        trie.insert("bat");

        System.out.println(trie.search("car"));  // true
        System.out.println(trie.search("bat"));  // true
        System.out.println(trie.search("can"));  // false
        System.out.println(trie.startsWith("ca")); // true
        trie.delete("car");
        System.out.println(trie.search("car"));  // false
    }
}

---

Trie Variants:

1. Compressed Trie (Radix Tree):
   Merges single-child nodes to reduce space usage.
2. Ternary Search Trie:
   Stores characters in a BST-like structure instead of a full tree.
3. Patricia Trie:
   A compact Trie optimized for routing tables.

---

Applications of Trie:

• Autocomplete: Predicts words based on prefix input.
• Spell Checking: Suggests corrections for misspelled words.
• IP Routing: Used in networking to match IP prefixes efficiently.
• Dictionary Implementation: Efficient word storage and lookup.

---

Summary

A Trie is a powerful data structure for storing and searching strings efficiently. Its fast lookup time and prefix search capabilities make it ideal for text processing, networking, and dictionary-based applications. However, it may consume more memory than hash tables, especially in naive implementations.

For memory-efficient alternatives, compressed tries and Radix trees can be used.