Every time you type in a search bar and see suggestions appear, a trie is probably working behind the scenes. A trie (pronounced “try”) is a tree-like data structure designed for fast string operations. It is the go-to data structure for autocomplete, spell checkers, and word search problems. In this article, you will learn how tries work, how to build one from scratch, and how to use them in coding interviews.

We show every example in Kotlin, Python, and Go.

What is a Trie?

A trie is a tree where each node represents a single character. Words are stored as paths from the root to a node marked as “end of word.” The root node is empty — it represents the start of all words.

Here is a trie containing the words “app”, “apple”, and “bat”:

        (root)
       /      \
      a        b
      |        |
      p        a
      |        |
      p*       t*
      |
      l
      |
      e*

Nodes marked with * are end-of-word markers.

Key properties:

  • Every path from root to an end node is a word
  • Common prefixes share the same path (efficient storage)
  • All operations take O(m) time, where m is the word length
  • The trie does not depend on the number of words stored

Trie Node Structure

Each node has:

  • A map of children (character -> child node)
  • A boolean flag to mark end of word

Python:

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False

Kotlin:

class TrieNode {
    val children = mutableMapOf<Char, TrieNode>()
    var isEnd = false
}

Go:

type TrieNode struct {
    Children map[byte]*TrieNode
    IsEnd    bool
}

func NewTrieNode() *TrieNode {
    return &TrieNode{Children: make(map[byte]*TrieNode)}
}

Implementing a Trie

Let’s build a trie with three operations: insert, search, and startsWith.

Insert

Walk through each character. If the character does not exist as a child, create a new node. After the last character, mark the node as end of word.

Walk through each character. If any character is missing, the word does not exist. If you reach the last character, check if it is marked as end of word.

Same as search, but you do not need the end-of-word check. If you can walk through all characters of the prefix, it exists.

Python:

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

    def insert(self, 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 = True

    def search(self, word):
        node = self._find(word)
        return node is not None and node.is_end

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

    def _find(self, text):
        node = self.root
        for char in text:
            if char not in node.children:
                return None
            node = node.children[char]
        return node

# Usage:
trie = Trie()
trie.insert("apple")
trie.insert("app")
print(trie.search("apple"))      # True
print(trie.search("app"))        # True
print(trie.search("ap"))         # False
print(trie.starts_with("ap"))    # True

Kotlin:

class Trie {
    private val root = TrieNode()

    fun insert(word: String) {
        var node = root
        for (char in word) {
            node = node.children.getOrPut(char) { TrieNode() }
        }
        node.isEnd = true
    }

    fun search(word: String): Boolean {
        val node = find(word)
        return node != null && node.isEnd
    }

    fun startsWith(prefix: String): Boolean {
        return find(prefix) != null
    }

    private fun find(text: String): TrieNode? {
        var node = root
        for (char in text) {
            node = node.children[char] ?: return null
        }
        return node
    }
}

Go:

type Trie struct {
    Root *TrieNode
}

func NewTrie() *Trie {
    return &Trie{Root: NewTrieNode()}
}

func (t *Trie) Insert(word string) {
    node := t.Root
    for i := 0; i < len(word); i++ {
        ch := word[i]
        if _, ok := node.Children[ch]; !ok {
            node.Children[ch] = NewTrieNode()
        }
        node = node.Children[ch]
    }
    node.IsEnd = true
}

func (t *Trie) Search(word string) bool {
    node := t.find(word)
    return node != nil && node.IsEnd
}

func (t *Trie) StartsWith(prefix string) bool {
    return t.find(prefix) != nil
}

func (t *Trie) find(text string) *TrieNode {
    node := t.Root
    for i := 0; i < len(text); i++ {
        ch := text[i]
        if _, ok := node.Children[ch]; !ok {
            return nil
        }
        node = node.Children[ch]
    }
    return node
}

Time and Space Complexity

OperationTimeSpace
InsertO(m)O(m)
SearchO(m)O(1)
StartsWithO(m)O(1)

Where m is the length of the word or prefix. These operations do not depend on how many words are in the trie.

Space for the entire trie: O(N * M) in the worst case, where N is the number of words and M is the average word length. In practice, shared prefixes reduce the space significantly.

Trie vs Hash Map

Both can store strings, but they solve different problems.

TrieHash Map
Exact searchO(m)O(m) average
Prefix searchO(m)Not possible without scanning all keys
AutocompleteNaturalRequires extra work
SpaceHigher (one node per char)Lower
Sorted iterationNatural (alphabetical)Not sorted

Use a trie when you need prefix operations. Use a hash map when you only need exact lookups.

Interview Problem: Implement Trie

This is LeetCode #208. We already built this above. The key insight interviewers test is whether you understand:

  1. Each node holds a map of children, not just left/right pointers
  2. End-of-word markers are necessary to distinguish “app” from “apple”
  3. All operations are O(m) regardless of trie size

Interview Problem: Word Search II

Given a board of characters and a list of words, find all words that can be formed by moving horizontally or vertically on the board. This is LeetCode #212.

Strategy: Insert all words into a trie. Then run DFS from each cell on the board, using the trie to prune paths that do not match any word prefix.

Python:

def find_words(board, words):
    trie = Trie()
    for word in words:
        trie.insert(word)

    rows, cols = len(board), len(board[0])
    result = set()

    def dfs(r, c, node, path):
        if r < 0 or r >= rows or c < 0 or c >= cols:
            return
        char = board[r][c]
        if char not in node.children:
            return

        node = node.children[char]
        path += char

        if node.is_end:
            result.add(path)

        board[r][c] = '#'  # Mark visited
        dfs(r + 1, c, node, path)
        dfs(r - 1, c, node, path)
        dfs(r, c + 1, node, path)
        dfs(r, c - 1, node, path)
        board[r][c] = char  # Restore

    for r in range(rows):
        for c in range(cols):
            dfs(r, c, trie.root, "")

    return list(result)

Kotlin:

fun findWords(board: Array<CharArray>, words: Array<String>): List<String> {
    val trie = Trie()
    for (word in words) trie.insert(word)

    val rows = board.size
    val cols = board[0].size
    val result = mutableSetOf<String>()

    fun dfs(r: Int, c: Int, node: TrieNode, path: StringBuilder) {
        if (r < 0 || r >= rows || c < 0 || c >= cols) return
        val char = board[r][c]
        val child = node.children[char] ?: return

        path.append(char)
        if (child.isEnd) result.add(path.toString())

        board[r][c] = '#'
        dfs(r + 1, c, child, path)
        dfs(r - 1, c, child, path)
        dfs(r, c + 1, child, path)
        dfs(r, c - 1, child, path)
        board[r][c] = char
        path.deleteCharAt(path.length - 1)
    }

    for (r in 0 until rows) {
        for (c in 0 until cols) {
            dfs(r, c, trie.root, StringBuilder())
        }
    }
    return result.toList()
}

Autocomplete with a Trie

One of the most practical uses of a trie is autocomplete. Given a prefix, find all words that start with it.

Python:

def autocomplete(trie, prefix):
    node = trie._find(prefix)
    if node is None:
        return []

    results = []

    def collect(node, path):
        if node.is_end:
            results.append(path)
        for char, child in node.children.items():
            collect(child, path + char)

    collect(node, prefix)
    return results

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

print(autocomplete(trie, "app"))
# Output: ["app", "apple", "application"]

Why Interviewers Ask Trie Questions

Trie questions test:

  1. Tree traversal skills — tries are trees, so DFS is the main tool
  2. Designing data structures — building a trie from scratch shows you understand nodes and pointers
  3. Optimization thinking — using a trie to prune search space (like in Word Search II)
  4. Real-world knowledge — autocomplete, spell check, and IP routing all use tries

Practice Problems

Try these on LeetCode:

  1. Implement Trie (#208) — build insert, search, startsWith
  2. Word Search II (#212) — DFS + trie pruning
  3. Design Add and Search Words (#211) — trie with wildcard ‘.’ support
  4. Replace Words (#648) — find shortest prefix in a trie
  5. Search Suggestions System (#1268) — trie-based autocomplete

What’s Next?

In the next article, we cover Union-Find (Disjoint Sets) — a data structure for efficiently grouping connected elements. Union-Find is the fastest way to solve connected components problems and appears in many graph-related interview questions.

Next: DSA Tutorial #9: Union-Find — Grouping Connected Elements

Full series: DSA from Zero to Interview Ready