What is a trie data structure? How do you implement it in Python?

Python Data Structures - Interview Questions and Answers

Trie Data Structure (Prefix Tree)

A Trie (pronounced "try") is a tree-based data structure used to store and search words efficiently. It's mainly used in applications like autocomplete, spell checking, and IP routing.

1. Why Use a Trie?

* Fast lookups – O(m) time complexity (where m = length of the word).
* Efficient storage – Common prefixes are stored once.
* Great for prefix-based searches – E.g., searching words starting with "ca" returns ["cat", "car", "cart"].

2. Trie Node Structure

Each node in a Trie contains:

A dictionary (children) for storing next letters.
A boolean (is_end_of_word) to mark the end of a word.

Implementation in Python

class TrieNode:
    def __init__(self):
        self.children = {}  # Dictionary to store child nodes
        self.is_end_of_word = False  # Marks if it's the end of a word

class Trie:
    def __init__(self):
        self.root = TrieNode()  # Root node (empty)

    def insert(self, word):
        """ Inserts a word into the Trie """
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()  # Create new node if not present
            node = node.children[char]  # Move to the next node
        node.is_end_of_word = True  # Mark last node as end of word

    def search(self, word):
        """ Returns True if the word is found in the Trie """
        node = self.root
        for char in word:
            if char not in node.children:
                return False  # Word not found
            node = node.children[char]
        return node.is_end_of_word  # Return True if it's an exact word

    def starts_with(self, prefix):
        """ Returns True if any word starts with the given prefix """
        node = self.root
        for char in prefix:
            if char not in node.children:
                return False  # Prefix not found
            node = node.children[char]
        return True  # Prefix found

# Example usage
trie = Trie()
trie.insert("cat")
trie.insert("car")
trie.insert("cart")

print(trie.search("car"))  # Output: True
print(trie.search("can"))  # Output: False
print(trie.starts_with("ca"))  # Output: True

3. Trie Operations & Complexity

Operation	Time Complexity
Insert	O(m)
Search	O(m)
Prefix Search	O(m)

* Faster than searching in lists or sets!

4. When to Use a Trie?

* Autocomplete & Spell Checking (Google Search, AutoCorrect).
* Word Dictionary (Lexicons, Word Games).
* IP Routing & Prefix Matching (Network Routing).