Trie (Prefix Tree) Visualizer

Instant Update

Select an operation

Words in trie: 5

Trie Structure

Root

End of Word

Highlighted Path

Logs

No operations yet

Notes

Trie is a tree-like data structure for efficient string searching.

Insert: Adds a word to the trie.

Search: Checks if a word exists in the trie.

Prefix Search: Finds all words with a given prefix.

Delete: Removes a word from the trie.

Green nodes indicate the end of a valid word.

The red node is the root of the trie.

Highlighted paths show the current operation.

Examples to try: cat, car, app, apple, tree, boot

Implementation (TypeScript)

class TrieNode {
  children: Map<string, TrieNode> = new Map();
  isEndOfWord: boolean = false;
}

class Trie {
  private root = new TrieNode();
  insert(word: string) {
    let current = this.root;
    for (const char of word) {
      if (!current.children.has(char)) {
        current.children.set(char, new TrieNode());
      }
      current = current.children.get(char)!;
    }
    current.isEndOfWord = true;
  }
  search(word: string): boolean {
    let current = this.root;
    for (const char of word) {
      if (!current.children.has(char)) return false;
      current = current.children.get(char)!;
    }
    return current.isEndOfWord;
  }
  startsWith(prefix: string): boolean {
    let current = this.root;
    for (const char of prefix) {
      if (!current.children.has(char)) return false;
      current = current.children.get(char)!;
    }
    return true;
  }
}

About Tries

A trie (prefix tree) is a specialized tree structure used for efficient string searching and prefix matching.

Applications:

Autocomplete systems
Spell checkers
IP routing tables
Dictionary implementations

Time Complexity:

Insert: O(m) where m is word length
Search: O(m) where m is word length
Prefix: O(p + n) where p is prefix length, n is number of results

Space Complexity: O(alphabet_size × number_of_nodes)