Tries (Prefix Trees) - Data Structures & Algorithms

A trie (pronounced “try”) is a tree-like data structure where each node represents a single character. We build words by walking down from the root, one character at a time. The name comes from “retrieval” — because tries are incredibly fast at looking up strings by prefix.

Why use a trie? Imagine we have a million words and we want to find all words starting with “app”. A hash map would need to check every single word. A trie just walks down the path a → p → p and everything below that node is a match. That’s the superpower of tries — prefix-based queries are lightning fast.

How a Trie Looks

Let’s say we insert the words: “cat”, “car”, “card”, “dog”, “do”.

Trie storing: "cat", "car", "card", "dog", "do"

root

╱╲

end

end |

end

end |

end

Nodes marked "end" indicate a complete word ends there.
"car" is a prefix of "card" — both share the same path down to 'r'.

Key observations:

The root is empty — it doesn’t represent any character.
Common prefixes share the same path. “cat” and “car” share c → a.
We mark nodes where a word ends with an isEnd flag. Without it, we couldn’t tell if “car” is a word or just a prefix of “card”.

Trie Node Definition

Each trie node has a map of children (character → child node) and a boolean marking if it’s the end of a word.

class TrieNode {
  constructor() {
    this.children = {};   // char -> TrieNode
    this.isEnd = false;   // does a word end here?
  }
}

class TrieNode:
    def __init__(self):
        self.children = {}   # char -> TrieNode
        self.is_end = False  # does a word end here?

class TrieNode {
    Map<Character, TrieNode> children = new HashMap<>();
    boolean isEnd = false;  // does a word end here?
}

Full Trie Implementation

The three core operations are insert, search, and startsWith (prefix check).

class Trie {
  constructor() { this.root = new TrieNode(); }

  insert(word) {
    let node = this.root;
    for (const ch of word) {
      if (!node.children[ch]) node.children[ch] = new TrieNode();
      node = node.children[ch]; // move down
    }
    node.isEnd = true; // mark end of word
  }

  search(word) {
    const node = this._findNode(word);
    return node !== null && node.isEnd; // must be end of word
  }

  startsWith(prefix) {
    return this._findNode(prefix) !== null; // just needs to exist
  }

  _findNode(str) {
    let node = this.root;
    for (const ch of str) {
      if (!node.children[ch]) return null; // path doesn't exist
      node = node.children[ch];
    }
    return node;
  }
}

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

    def insert(self, word):
        node = self.root
        for ch in word:
            if ch not in node.children:
                node.children[ch] = TrieNode()
            node = node.children[ch]  # move down
        node.is_end = True  # mark end of word

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

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

    def _find_node(self, s):
        node = self.root
        for ch in s:
            if ch not in node.children: return None
            node = node.children[ch]
        return node

class Trie {
    TrieNode root = new TrieNode();

    void insert(String word) {
        TrieNode node = root;
        for (char ch : word.toCharArray()) {
            node.children.putIfAbsent(ch, new TrieNode());
            node = node.children.get(ch); // move down
        }
        node.isEnd = true; // mark end of word
    }

    boolean search(String word) {
        TrieNode node = findNode(word);
        return node != null && node.isEnd;
    }

    boolean startsWith(String prefix) {
        return findNode(prefix) != null;
    }

    private TrieNode findNode(String s) {
        TrieNode node = root;
        for (char ch : s.toCharArray()) {
            if (!node.children.containsKey(ch)) return null;
            node = node.children.get(ch);
        }
        return node;
    }
}

Time for all operations: O(m) where m is the length of the word/prefix. Space: O(n * m) where n is the number of words.

Autocomplete with a Trie

This is where tries really shine. Given a prefix, find all words that start with it. We walk down to the prefix node, then do a DFS to collect all words below.

function autocomplete(trie, prefix) {
  const node = trie._findNode(prefix);
  if (!node) return [];                // prefix not in trie
  const results = [];
  function dfs(current, path) {
    if (current.isEnd) results.push(path);
    for (const [ch, child] of Object.entries(current.children))
      dfs(child, path + ch);
  }
  dfs(node, prefix);
  return results;
}
// autocomplete(trie, "ca") → ["cat", "car", "card"]

def autocomplete(trie, prefix):
    node = trie._find_node(prefix)
    if not node: return []              # prefix not in trie
    results = []
    def dfs(current, path):
        if current.is_end: results.append(path)
        for ch, child in current.children.items():
            dfs(child, path + ch)
    dfs(node, prefix)
    return results
# autocomplete(trie, "ca") → ["cat", "car", "card"]

List<String> autocomplete(Trie trie, String prefix) {
    TrieNode node = trie.findNode(prefix);
    List<String> results = new ArrayList<>();
    if (node == null) return results;    // prefix not in trie
    dfs(node, new StringBuilder(prefix), results);
    return results;
}
void dfs(TrieNode node, StringBuilder path, List<String> results) {
    if (node.isEnd) results.add(path.toString());
    for (var entry : node.children.entrySet()) {
        path.append(entry.getKey());
        dfs(entry.getValue(), path, results);
        path.deleteCharAt(path.length() - 1);
    }
}
// autocomplete(trie, "ca") → ["cat", "car", "card"]

Trie vs Hash Map

When should we use a trie instead of a hash set or map?

Feature	Hash Map	Trie
Exact lookup	O(m) — hash the key	O(m) — walk the path
Prefix search	O(n * m) — check every key	O(m + k) — walk prefix, collect matches
Sorted iteration	Not possible	Natural alphabetical order (DFS)
Space	Lower for few long strings	Can be large but shares prefixes
Autocomplete	Impractical	Built for this

In simple language: if we need prefix-based operations (autocomplete, spell check, IP routing), use a trie. For simple key-value lookups, a hash map is simpler and usually faster.

Word Search in a Board

A classic hard interview problem: given a 2D board of characters and a list of words, find all words that can be formed by adjacent cells. The trick is to build a trie from the word list, then DFS on the board using the trie to prune dead-end paths early.

function findWords(board, words) {
  const trie = new Trie();
  for (const w of words) trie.insert(w);
  const result = new Set(), rows = board.length, cols = board[0].length;

  function dfs(r, c, node, path) {
    if (node.isEnd) result.add(path);
    if (r < 0 || r >= rows || c < 0 || c >= cols) return;
    const ch = board[r][c];
    if (ch === '#' || !node.children[ch]) return;
    board[r][c] = '#'; // mark visited
    const next = node.children[ch];
    for (const [dr, dc] of [[0,1],[0,-1],[1,0],[-1,0]])
      dfs(r + dr, c + dc, next, path + ch);
    board[r][c] = ch; // restore
  }
  for (let r = 0; r < rows; r++)
    for (let c = 0; c < cols; c++)
      dfs(r, c, trie.root, "");
  return [...result];
}

def find_words(board, words):
    trie = Trie()
    for w in words: trie.insert(w)
    result, rows, cols = set(), len(board), len(board[0])

    def dfs(r, c, node, path):
        if node.is_end: result.add(path)
        if r < 0 or r >= rows or c < 0 or c >= cols: return
        ch = board[r][c]
        if ch == '#' or ch not in node.children: return
        board[r][c] = '#'  # mark visited
        nxt = node.children[ch]
        for dr, dc in [(0,1),(0,-1),(1,0),(-1,0)]:
            dfs(r + dr, c + dc, nxt, path + ch)
        board[r][c] = ch   # restore
    for r in range(rows):
        for c in range(cols):
            dfs(r, c, trie.root, "")
    return list(result)

// Simplified — uses same Trie class from above
Set<String> findWords(char[][] board, String[] words) {
    Trie trie = new Trie();
    for (String w : words) trie.insert(w);
    Set<String> result = new HashSet<>();
    for (int r = 0; r < board.length; r++)
        for (int c = 0; c < board[0].length; c++)
            dfs(board, r, c, trie.root, "", result);
    return result;
}
void dfs(char[][] board, int r, int c, TrieNode node,
         String path, Set<String> result) {
    if (node.isEnd) result.add(path);
    if (r<0||r>=board.length||c<0||c>=board[0].length) return;
    char ch = board[r][c];
    if (ch=='#'||!node.children.containsKey(ch)) return;
    board[r][c] = '#';
    TrieNode next = node.children.get(ch);
    int[][] dirs = {{0,1},{0,-1},{1,0},{-1,0}};
    for (int[] d : dirs)
        dfs(board, r+d[0], c+d[1], next, path+ch, result);
    board[r][c] = ch;
}

Key Takeaways

A trie stores strings character by character in a tree structure. Common prefixes share nodes.
The three core operations (insert, search, startsWith) all run in O(m) time where m is the string length.
Tries are the go-to for prefix queries, autocomplete, and spell checking.
The isEnd flag is critical — without it we can’t distinguish complete words from prefixes.
For the word search board problem, a trie lets us prune entire branches of invalid paths during DFS.

In simple language, a trie is a tree optimized for strings. It trades space for blazing-fast prefix lookups. When we hear “prefix,” “autocomplete,” or “dictionary,” we should think trie.