Trie Data Structure: Implementation and Applications

A Trie (pronounced “try”) is a tree-like data structure used to store and retrieve strings efficiently. Unlike a binary search tree where each node holds a complete key, each node in a Trie represents a single character. Paths from the root to marked nodes form complete words. This makes Tries exceptionally fast for prefix-based operations.

Why Tries exist

You could store strings in a hash set and get O(1) average lookups. So why use a Trie?

• Prefix queries: “Give me all words starting with ‘pre’” is O(p + k) where p is the prefix length and k is the number of matches. A hash set cannot do this without scanning every entry.
• Ordered iteration: A Trie naturally stores words in lexicographic order.
• No hash collisions: Lookups are always O(m) where m is the word length, with no worst-case degradation.
• Space efficiency for shared prefixes: Words like “prefix”, “preorder”, “preview” share the “pre” path.

Basic implementation in Python

class TrieNode:
    def __init__(self):
        self.children = {}       # char -> TrieNode
        self.is_end_of_word = False

class Trie:
    def __init__(self):
        self.root = TrieNode()
    
    def insert(self, word: str) -> None:
        """Insert a word into the trie. O(m) where m = len(word)."""
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_end_of_word = True
    
    def search(self, word: str) -> bool:
        """Check if a word exists in the trie. O(m)."""
        node = self._find_node(word)
        return node is not None and node.is_end_of_word
    
    def starts_with(self, prefix: str) -> bool:
        """Check if any word starts with the given prefix. O(m)."""
        return self._find_node(prefix) is not None
    
    def _find_node(self, prefix: str) -> TrieNode | None:
        """Navigate to the node representing the end of the prefix."""
        node = self.root
        for char in prefix:
            if char not in node.children:
                return None
            node = node.children[char]
        return node

Using the Trie

trie = Trie()

# insert words
words = ["apple", "app", "application", "apply", "banana", "band", "bandana"]
for word in words:
    trie.insert(word)

# search
print(trie.search("apple"))       # True
print(trie.search("app"))         # True
print(trie.search("ap"))          # False (not a complete word)
print(trie.search("orange"))      # False

# prefix check
print(trie.starts_with("app"))    # True
print(trie.starts_with("ban"))    # True
print(trie.starts_with("cat"))    # False

Collecting all words with a prefix

This is the core operation for autocomplete:

class Trie:
    # ... previous methods ...
    
    def words_with_prefix(self, prefix: str) -> list[str]:
        """Return all words that start with the given prefix."""
        node = self._find_node(prefix)
        if node is None:
            return []
        
        results = []
        self._collect_words(node, prefix, results)
        return results
    
    def _collect_words(self, node: TrieNode, current: str, results: list) -> None:
        """DFS to collect all complete words from this node."""
        if node.is_end_of_word:
            results.append(current)
        
        for char in sorted(node.children):  # sorted for lexicographic order
            self._collect_words(node.children[char], current + char, results)

trie = Trie()
for word in ["apple", "app", "application", "apply", "banana", "band"]:
    trie.insert(word)

print(trie.words_with_prefix("app"))
# ['app', 'apple', 'application', 'apply']

print(trie.words_with_prefix("ban"))
# ['banana', 'band']

print(trie.words_with_prefix("cat"))
# []

Deletion

Deleting from a Trie is trickier than insertion because you need to clean up nodes that are no longer part of any word:

class Trie:
    # ... previous methods ...
    
    def delete(self, word: str) -> bool:
        """Delete a word from the trie. Returns True if the word existed."""
        return self._delete(self.root, word, 0)
    
    def _delete(self, node: TrieNode, word: str, depth: int) -> bool:
        if depth == len(word):
            if not node.is_end_of_word:
                return False  # word does not exist
            node.is_end_of_word = False
            return True
        
        char = word[depth]
        if char not in node.children:
            return False
        
        deleted = self._delete(node.children[char], word, depth + 1)
        
        # clean up: remove child if it has no children and is not end of another word
        child = node.children[char]
        if deleted and not child.is_end_of_word and not child.children:
            del node.children[char]
        
        return deleted

trie = Trie()
for word in ["apple", "app", "application"]:
    trie.insert(word)

trie.delete("application")
print(trie.search("application"))  # False
print(trie.search("apple"))        # True (not affected)
print(trie.search("app"))          # True (not affected)

trie.delete("app")
print(trie.search("app"))          # False
print(trie.search("apple"))        # True (shared prefix preserved)

Java implementation

import java.util.*;

class Trie {
    private static class TrieNode {
        Map<Character, TrieNode> children = new HashMap<>();
        boolean isEndOfWord = false;
    }
    
    private final TrieNode root = new TrieNode();
    
    public void insert(String word) {
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            node.children.putIfAbsent(c, new TrieNode());
            node = node.children.get(c);
        }
        node.isEndOfWord = true;
    }
    
    public boolean search(String word) {
        TrieNode node = findNode(word);
        return node != null && node.isEndOfWord;
    }
    
    public boolean startsWith(String prefix) {
        return findNode(prefix) != null;
    }
    
    private TrieNode findNode(String prefix) {
        TrieNode node = root;
        for (char c : prefix.toCharArray()) {
            if (!node.children.containsKey(c)) return null;
            node = node.children.get(c);
        }
        return node;
    }
    
    public List<String> wordsWithPrefix(String prefix) {
        List<String> results = new ArrayList<>();
        TrieNode node = findNode(prefix);
        if (node != null) {
            collectWords(node, new StringBuilder(prefix), results);
        }
        return results;
    }
    
    private void collectWords(TrieNode node, StringBuilder current, List<String> results) {
        if (node.isEndOfWord) {
            results.add(current.toString());
        }
        for (char c : new TreeSet<>(node.children.keySet())) {
            current.append(c);
            collectWords(node.children.get(c), current, results);
            current.deleteCharAt(current.length() - 1);
        }
    }
}

Autocomplete system

A practical autocomplete ranks suggestions by frequency:

class AutocompleteTrie:
    def __init__(self):
        self.root = TrieNode()
        self.word_count = {}  # word -> frequency
    
    def add_word(self, word: str, count: int = 1) -> None:
        """Add a word with its frequency count."""
        node = self.root
        for char in word.lower():
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_end_of_word = True
        self.word_count[word.lower()] = self.word_count.get(word.lower(), 0) + count
    
    def autocomplete(self, prefix: str, max_results: int = 5) -> list[str]:
        """Return top suggestions sorted by frequency."""
        prefix = prefix.lower()
        node = self.root
        for char in prefix:
            if char not in node.children:
                return []
            node = node.children[char]
        
        # collect all words
        candidates = []
        self._collect(node, prefix, candidates)
        
        # sort by frequency (descending) and return top results
        candidates.sort(key=lambda w: self.word_count.get(w, 0), reverse=True)
        return candidates[:max_results]
    
    def _collect(self, node, current, results):
        if node.is_end_of_word:
            results.append(current)
        for char in node.children:
            self._collect(node.children[char], current + char, results)

# usage
ac = AutocompleteTrie()
search_data = [
    ("python tutorial", 1500),
    ("python list", 1200),
    ("python dictionary", 900),
    ("python string methods", 800),
    ("pytorch", 600),
    ("pycharm", 400),
]

for word, count in search_data:
    ac.add_word(word, count)

print(ac.autocomplete("py", 3))
# ['python tutorial', 'python list', 'python dictionary']

print(ac.autocomplete("python d"))
# ['python dictionary']

Word search in a board (LeetCode 212)

Tries are the standard solution for the word search II problem:

def find_words(board: list[list[str]], words: list[str]) -> list[str]:
    # build trie from word list
    root = TrieNode()
    for word in words:
        node = root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_end_of_word = True
        node.word = word  # store the complete word at the end node
    
    rows, cols = len(board), len(board[0])
    found = set()
    
    def dfs(r, c, node):
        if r < 0 or r >= rows or c < 0 or c >= cols:
            return
        
        char = board[r][c]
        if char == "#" or char not in node.children:
            return
        
        next_node = node.children[char]
        if next_node.is_end_of_word:
            found.add(next_node.word)
        
        # mark visited
        board[r][c] = "#"
        
        for dr, dc in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
            dfs(r + dr, c + dc, next_node)
        
        # restore
        board[r][c] = char
    
    for r in range(rows):
        for c in range(cols):
            dfs(r, c, root)
    
    return list(found)

Complexity analysis

Operation	Time	Space
Insert	O(m)	O(m) per word
Search	O(m)	O(1)
Prefix check	O(m)	O(1)
Delete	O(m)	O(1)
Collect all with prefix	O(p + k*m)	O(k*m)
Total space	-	O(n * m) worst case

Where m = word length, n = number of words, p = prefix length, k = number of matches.

When to use a Trie

Use a Trie when you need prefix queries, autocomplete, or dictionary operations where shared prefixes are common. For simple membership checks without prefix operations, a hash set is simpler and usually faster. For sorted string storage without prefix queries, a balanced BST or sorted array works fine. The Trie earns its place when prefix-based access patterns dominate.