Trie

Data Structures

avgO(L)worstO(L)spaceO(total letters)

An empty trie: just the root

1 / 40

Code

class TrieNode {  children = new Map<string, TrieNode>();  end = false;}class Trie {  root = new TrieNode();  insert(word: string) {    let node = this.root;    for (const ch of word) {      if (!node.children.has(ch)) node.children.set(ch, new TrieNode());      node = node.children.get(ch)!;    }    node.end = true;  }  search(word: string) {    let node = this.root;    for (const ch of word) {      const next = node.children.get(ch);      if (!next) return false;      node = next;    }    return node.end;  }}

structure TrieNode  children ← empty map from letter to node  end ← falseend structurestructure Trie  root ← new TrieNode  procedure insert(word)    node ← root    for each letter ch in word do      if node has no child ch then add a new child ch      node ← node.children[ch]    end for    node.end ← true    ▷ a word ends here  end procedure  procedure search(word)    node ← root    for each letter ch in word do      next ← node.children[ch]      if next = null then return false      node ← next    end for    return node.end    ▷ a prefix alone is not a word  end procedureend structure

Variables

none

Counters

nodes created: 0
steps: 0

Operations8 / 40

1. insert("car")
2. insert("cat")
3. insert("cart")
4. insert("dog")
5. insert("do")
6. search("cat")
7. search("ca")
8. search("dot")

How it works

A prefix tree: each edge is a letter and each path from the root spells a prefix, so words that share a prefix share nodes. Insert and search take O(L) for a word of length L, independent of how many words are stored. A flag marks where whole words end.

Complexity

Best: O(L)
Average: O(L)
Worst: O(L)
Space: O(total letters)

Trie

How it works

Complexity

Search algorithms