Tries

Prefix trees for fast autocomplete, dictionary lookup, and word search.

Tries Operations & Functions

Trie functions

These are the building blocks you reach for in interview trie problems — insert a word, check a full match, check a prefix, or collect completions.

Prefer Overview for how tries grow and share paths, and Problems for practice once problems are linked.

Node & root

A trie is a tree of nodes. Each edge is one character; a flag marks a finished word.

TrieNode

One node: a map of next letters, plus whether a word ends here.

trie-node.tsTypeScript
type TrieNode = {
  children: Map<string, TrieNode>;
  end: boolean;
};

function createNode(): TrieNode {
  return { children: new Map(), end: false };
}

// ——— root starts empty ———
const root = createNode();

Array children[26]

Fixed alphabet (a–z) can use an array of 26 slots instead of a Map.

trie-node-array.tsTypeScript
type TrieNode26 = {
  children: (TrieNode26 | null)[];
  end: boolean;
};

function createNode26(): TrieNode26 {
  return { children: Array(26).fill(null), end: false };
}

function indexOf(ch: string): number {
  return ch.charCodeAt(0) - 97; // 'a' → 0
}

Insert

Walk one letter at a time. Create a child when the edge is missing, then mark the end.

insert()

Adds a word. Shared prefixes reuse existing nodes.

trie-insert.tsTypeScript
function insert(root: TrieNode, word: string): void {
  let node = root;
  for (const ch of word) {
    let next = node.children.get(ch);
    if (!next) {
      next = createNode();
      node.children.set(ch, next);
    }
    node = next;
  }
  node.end = true;
}

insert(root, 'cat');
insert(root, 'car'); // reuses c → a

Follow every letter. The word is present only if you land on a node marked end.

search()

Returns true only for a full word, not a bare prefix.

trie-search.tsTypeScript
function search(root: TrieNode, word: string): boolean {
  let node = root;
  for (const ch of word) {
    const next = node.children.get(ch);
    if (!next) return false;
    node = next;
  }
  return node.end;
}

search(root, 'cat'); // true
search(root, 'ca');  // false — prefix only
search(root, 'cab'); // false — missing edge

Prefix / startsWith

Same walk as search, but you only need the path to exist — end flag does not matter.

startsWith()

True if any inserted word begins with the given prefix.

trie-starts-with.tsTypeScript
function startsWith(root: TrieNode, prefix: string): boolean {
  let node = root;
  for (const ch of prefix) {
    const next = node.children.get(ch);
    if (!next) return false;
    node = next;
  }
  return true;
}

startsWith(root, 'ca');  // true
startsWith(root, 'car'); // true
startsWith(root, 'cu');  // false

findNode()

Walk to the node for a prefix (or null). Handy before autocomplete.

trie-find-node.tsTypeScript
function findNode(
  root: TrieNode,
  prefix: string,
): TrieNode | null {
  let node = root;
  for (const ch of prefix) {
    const next = node.children.get(ch);
    if (!next) return null;
    node = next;
  }
  return node;
}

Build from a word list

Most problems give you a dictionary up front. Insert every word once, then query.

buildTrie()

Creates a root and inserts every word from a list.

trie-build.tsTypeScript
function buildTrie(words: string[]): TrieNode {
  const root = createNode();
  for (const word of words) {
    insert(root, word);
  }
  return root;
}

const trie = buildTrie(['cat', 'car', 'card', 'care']);

Autocomplete collect

Reach the prefix node, then DFS every descendant that ends a word.

collect()

Depth-first walk that gathers full words under a node.

trie-collect.tsTypeScript
function collect(
  node: TrieNode,
  path: string,
  out: string[],
): void {
  if (node.end) out.push(path);
  for (const [ch, child] of node.children) {
    collect(child, path + ch, out);
  }
}

function autocomplete(
  root: TrieNode,
  prefix: string,
): string[] {
  const node = findNode(root, prefix);
  if (!node) return [];
  const out: string[] = [];
  collect(node, prefix, out);
  return out;
}

autocomplete(trie, 'car'); // ['car', 'card', 'care']

delete() (optional)

Clear the end mark; prune a child only when it has no further use.

trie-delete.tsTypeScript
function remove(
  node: TrieNode,
  word: string,
  i = 0,
): boolean {
  if (i === word.length) {
    if (!node.end) return false;
    node.end = false;
    return node.children.size === 0;
  }

  const ch = word[i]!;
  const child = node.children.get(ch);
  if (!child) return false;

  const shouldPrune = remove(child, word, i + 1);
  if (shouldPrune) node.children.delete(ch);
  return !node.end && node.children.size === 0;
}

remove(root, 'cat');

Related concepts