EthicsComputerCourses
Join training
  1. Tutorials
  2. Data Structures & Algorithms
  3. Trees

Tries

DSA · Lesson 21 of 34 7 min read Updated

When you type "Lu" into a railway booking site and it suggests Lucknow, Ludhiana and Lumding, the site is answering a prefix question: which words start with these letters? A hash table cannot answer that directly, because it only finds exact keys. A trie (from "retrieval", usually pronounced "try"), also called a prefix tree, is built for exactly this job.

In this lesson you will build a trie for city names, use it for exact search and prefix search, write an autocomplete that ranks suggestions, keep prefix counts and delete words. You will also see a simpler alternative using a sorted list.

How a trie stores words

A trie is a tree where each edge is labelled with one character. Each path from the root spells out the beginning of one or more words. Words that share a prefix share the same path, so "Pune" and "Puri" share the nodes for "P" and "Pu", and only split at the third letter.

Each node needs two things: a dictionary from characters to child nodes, and a flag that says "a word ends here". The flag is needed because one word can be a prefix of another, such as "Goa" and "Goalpara".

PythonRun it yourself
class TrieNode:
    def __init__(self):
        self.children = {}          # character -> TrieNode
        self.is_word = False

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        node = self.root
        for ch in word.lower():
            node = node.children.setdefault(ch, TrieNode())
        node.is_word = True

    def _walk(self, text):
        node = self.root
        for ch in text.lower():
            node = node.children.get(ch)
            if node is None:
                return None
        return node

    def contains(self, word):
        node = self._walk(word)
        return node is not None and node.is_word

    def starts_with(self, prefix):
        return self._walk(prefix) is not None

cities = Trie()
for city in ["Pune", "Puri", "Patna", "Panaji", "Goa", "Goalpara", "Gorakhpur"]:
    cities.insert(city)

print(cities.contains("Puri"), cities.contains("Pur"))
print(cities.starts_with("Pur"), cities.starts_with("Pul"))
print(cities.contains("Goa"), cities.contains("goalpara"))
Output
True False
True False
True True

"Pur" is a valid prefix (of "Puri") but not a word, because the node for "r" is not marked. Each operation walks one node per character, so insert, search and prefix search all cost O(L) for a word or prefix of length L, no matter how many words the trie holds.

Autocomplete

To suggest completions, walk to the node for the prefix, then explore everything below it with a depth-first search, collecting every complete word. Visiting the children in sorted order gives alphabetical suggestions.

PythonRun it yourself
class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_word = False

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        node = self.root
        for ch in word.lower():
            node = node.children.setdefault(ch, TrieNode())
        node.is_word = True

    def suggest(self, prefix, limit=5):
        node = self.root
        for ch in prefix.lower():
            if ch not in node.children:
                return []
            node = node.children[ch]
        results = []

        def collect(n, path):
            if len(results) == limit:
                return                          # stop early
            if n.is_word:
                results.append(path)
            for ch in sorted(n.children):
                collect(n.children[ch], path + ch)

        collect(node, prefix.lower())
        return results

stations = Trie()
for s in ["Lucknow", "Ludhiana", "Lumding", "Lonavala", "Latur",
          "Lalitpur", "Lucknow Junction", "Lunkaransar"]:
    stations.insert(s)

print(stations.suggest("Lu"))
print(stations.suggest("Luc"))
print(stations.suggest("La"))
print(stations.suggest("Lx"))
Output
['lucknow', 'lucknow junction', 'ludhiana', 'lumding', 'lunkaransar']
['lucknow', 'lucknow junction']
['lalitpur', 'latur']
[]

Finding the prefix node costs O(L); collecting costs time proportional to the size of that subtree, and the limit stops the search as soon as there are enough suggestions. The space character in "Lucknow Junction" is just another character in the trie.

Ranking suggestions by popularity

Real autocomplete shows the most searched words first. Store a count on each word's end node, and also a prefix_count on every node: the number of words passing through it. That second number answers "how many words start with this prefix?" in O(L) without exploring anything.

PythonRun it yourself
import heapq

class TrieNode:
    def __init__(self):
        self.children = {}
        self.searches = 0           # > 0 means a word ends here
        self.prefix_count = 0       # words that pass through this node

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def add(self, word, searches):
        node = self.root
        for ch in word:
            node = node.children.setdefault(ch, TrieNode())
            node.prefix_count += 1
        node.searches += searches

    def _find(self, prefix):
        node = self.root
        for ch in prefix:
            node = node.children.get(ch)
            if node is None:
                return None
        return node

    def count_prefix(self, prefix):
        node = self._find(prefix)
        return node.prefix_count if node else 0

    def top(self, prefix, k):
        node = self._find(prefix)
        if node is None:
            return []
        found, stack = [], [(node, prefix)]
        while stack:                           # iterative DFS
            n, word = stack.pop()
            if n.searches:
                found.append((n.searches, word))
            for ch, child in n.children.items():
                stack.append((child, word + ch))
        return [w for _, w in heapq.nlargest(k, found)]

dishes = Trie()
for dish, n in [("paneer tikka", 940), ("paneer butter masala", 1210),
                ("pav bhaji", 1530), ("pani puri", 870), ("paratha", 660),
                ("pasta", 410)]:
    dishes.add(dish, n)

print(dishes.top("pa", 3))
print(dishes.top("paneer", 3))
print(dishes.count_prefix("pa"), dishes.count_prefix("pan"), dishes.count_prefix("pi"))
Output
['pav bhaji', 'paneer butter masala', 'paneer tikka']
['paneer butter masala', 'paneer tikka']
6 3 0

This version uses an explicit stack instead of recursion, so very long words cannot hit the recursion limit, and heapq.nlargest() from Heaps & Priority Queues picks the top k.

Deleting a word

To delete, unmark the end node. Then, on the way back up, remove any node that is no longer part of any word: it is not marked and has no children. Recursion makes the "on the way back up" part natural.

PythonRun it yourself
class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_word = False

def insert(root, word):
    node = root
    for ch in word:
        node = node.children.setdefault(ch, TrieNode())
    node.is_word = True

def delete(node, word, i=0):
    """Remove word; return True if this node can now be removed too."""
    if i == len(word):
        node.is_word = False
    else:
        child = node.children.get(word[i])
        if child and delete(child, word, i + 1):
            del node.children[word[i]]
    return not node.is_word and not node.children

def count_nodes(node):
    return 1 + sum(count_nodes(c) for c in node.children.values())

root = TrieNode()
for w in ["goa", "goalpara", "gonda"]:
    insert(root, w)
print("nodes:", count_nodes(root))
delete(root, "goalpara")
print("nodes after deleting goalpara:", count_nodes(root))
delete(root, "goa")
print("nodes after deleting goa:", count_nodes(root))
Output
nodes: 12
nodes after deleting goalpara: 7
nodes after deleting goa: 6

The trie starts with 12 nodes: the root, eight nodes for "goalpara" (the first three are shared with "goa") and three more for "gonda", which shares "go". Deleting "goalpara" removed its five private nodes ("l", "p", "a", "r", "a") and stopped at the "a" of "goa", because that node still marks a word. Deleting "goa" unmarked that "a"; it then had no children either, so it was removed too. The "g" and "o" nodes stayed, because "gonda" still needs them.

A simpler alternative: sorted list and bisect

For a fixed list of words, you can get prefix search without a trie. In a sorted list, all words that start with a prefix sit next to each other. bisect_left() finds the first one in O(log n) (see Binary Search & Its Variants):

PythonRun it yourself
import bisect

words = sorted(["lucknow", "ludhiana", "lumding", "lonavala", "latur", "lalitpur"])

def with_prefix(prefix):
    start = bisect.bisect_left(words, prefix)
    out = []
    for w in words[start:]:
        if not w.startswith(prefix):
            break
        out.append(w)
    return out

print(with_prefix("lu"))
print(with_prefix("la"))
Output
['lucknow', 'ludhiana', 'lumding']
['lalitpur', 'latur']
NeedBest choice
Exact lookups onlyset or dict
Prefix search on a fixed word listSorted list with bisect
Prefix search with frequent inserts and deletes, prefix counts or per-letter logicTrie

Tries use a lot of memory, one dictionary per node. Production systems often use a compressed trie (radix tree), which merges chains of single-child nodes into one edge labelled with a whole string.

Common mistakes

  • Forgetting the end-of-word flag. Without it, every prefix looks like a word.
  • Mixing letter cases. Normalise with lower() on both insert and search.
  • Using a trie when a set would do. For exact lookups, a set is simpler and uses far less memory.
  • Deleting nodes that other words still use. Only remove nodes that are unmarked and have no children.

Key points

  • A trie stores words along root-to-node paths, so words with a common prefix share nodes.
  • Each node holds a children dictionary and an end-of-word flag.
  • Insert, search and prefix check cost O(L) for a word of length L, independent of the number of words.
  • Autocomplete walks to the prefix node, then collects words below it; counts on nodes allow ranking and prefix counting.
  • A sorted list with bisect handles prefix search on fixed data; a trie shines when words change often.

Exercise

Write longest_common_prefix(words) using a trie: insert all the words, then walk down from the root while the current node has exactly one child and is not the end of a word. Test it with ["interview", "internet", "interval", "internal"] and ["dsa", "java"].

Show solution
Python
class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_word = False

def longest_common_prefix(words):
    root = TrieNode()
    for w in words:
        node = root
        for ch in w:
            node = node.children.setdefault(ch, TrieNode())
        node.is_word = True
    prefix, node = "", root
    while len(node.children) == 1 and not node.is_word:
        ch, node = next(iter(node.children.items()))
        prefix += ch
    return prefix

print(repr(longest_common_prefix(["interview", "internet", "interval", "internal"])))
print(repr(longest_common_prefix(["dsa", "java"])))
Output
'inter'
''

The common prefix ends where the trie first branches or where a word ends. For "dsa" and "java" the root already has two children, so the prefix is empty.

Quick Quiz

1. What does the end-of-word flag in a trie node tell you?

2. What is the cost of checking whether a prefix of length L exists in a trie of n words?

3. Which is the simplest good choice when you only need exact word lookups?

4. In a sorted list, why are all words with the same prefix next to each other?

Learn DSA with a mentor

Free lessons get you started. Our Java, C & C++ Programming training adds real projects and code reviews from working developers.

  • Project-based learning
  • Mentor code reviews
  • Free counselling call
Get course details +91 90532 10052