Trees - Trie

All about Trie Trees

A Trie (pronounced “try”) is a tree-based data structure that is used to efficiently store and retrieve strings — typically when dealing with large dictionaries or prefix-based queries.

Instead of storing words independently, Trie organizes them by their common prefixes, allowing fast lookups for both complete words and prefixes.

This structure is perfect for problems like autocomplete systems, spell checkers, prefix-based searches, building dictionaries.

LinkIconApproach

We define a TrieNode class with the following properties:

  1. letter: string
  2. isEndOfWord: boolean
  3. children: Map<letter, TrieNode> (a map of the next letters as Nodes)

We define a Trie class with three main operations:

  1. Insert(word)
  • Start from the root node.
  • For each character in the word, move down the Trie — if a node for that character doesn’t exist, create it.
  • After inserting all characters, mark the final node as endOfWord = True to indicate the completion of a valid word.
  1. Search(word)
  • Traverse the Trie character by character.
  • If a character doesn’t exist in the current node’s children, return False.
  • If all characters are found, return True only if the last node marks the end of a word.
  1. startsWith(prefix)
  • Similar to search, but we only check whether all characters in the prefix exist in the Trie.
  • We don’t require the final node to be an end of a complete word.
  • Each Trie node is represented by a dictionary (children) mapping characters to child nodes and a boolean flag (endOfWord) indicating if a word ends there.

LinkIconTime Complexity

Time complexity: L is the length of the word or prefix.

  • insert(word) → O(L)
  • search(word) → O(L)
  • startsWith(prefix) → O(L)

Space complexity: N is the number of words inserted and L is their average length (for storing Trie nodes).

  • O(N×L),

LinkIconImplemmentation with Nodes

Each node stores:

  • A map of child nodes (for each character)
  • A flag isEndOfWord indicating whether the path forms a complete word.
(root)
 └── c
      └── a
           ├── r (end)
           │    └── t (end)
           └── t (end)
class TrieNode {
  constructor(word) {
    this.word = word
    this.isEndOfWord = false;
    this.children = new Map(); // Map<char, TrieNode>
  }
}
class Trie {
  constructor() {
    this.root = new TrieNode("");
  }
 
  insert(word) {
    let currentNode = this.root
    for (const letter of word) {
      if (!(currentNode.children.has(letter))) {
        currentNode.children.set(letter, new TrieNode(letter))
      }
      let nextNode = currentNode.children.get(letter) 
      currentNode = nextNode
    }
 
    currentNode.isEndWord = true
  }
 
  search(word) {
    let currentNode = this.root
    for (const letter of word) {
      if (!currentNode.children.has(letter)) return false
 
      let nextNode = currentNode.children.get(letter)
      currentNode = nextNode
    }
    return currentNode.isEndWord
  }
 
  delete(word) {
    let currentNode = this.root;
    for (const letter of word) {
      if (!currentNode.children.has(letter)) return false;
      
      currentNode = currentNode.children.get(letter);
    }
 
    if (currentNode.isEndOfWord === false) return false
    
    currentNode.isEndOfWord = false
    return true
  }
}

LinkIconImplementation with Objects

Each key stores:

  • An object with keys for each character
  • A flag key * indicating whether the path forms a complete word.
(root) {
    b: {
      e: {
        a: { r: { *: true }}, // bear
        l: { l: { *: true }} // bell
      }
      i: { d: { *: true }} // bid
      u: {
        l: { l: { *: true }}, // bull
        y: { *: true } // buy
      }
    },
    s: {
      e: {
        l: { l: { *: true}} // sell
      },
      t: {
        o: {
          p: { *: true }, // stop
          c: { k: { *: true }}  // stock
        },
      }
    }
  }
class Trie {
  constructor() {
    this.root = {}
    // end of word character = "*"
  }
 
  insert(word: string): void {
    let node = this.root;
    for (const char of word) {
      if (!(char in node)) {
        node[char] = {};
      }
      node = node[char];
    }
    node['*'] = true;
  }
 
  search(word: string): boolean {
    let node = this.root;
    for (const char of word) {
      if (!(char in node)) return false;
      node = node[char];
    }
    return !!node['*'];
  }
 
  startsWith(prefix: string): boolean {
    let node = this.root;
    for (const char of prefix) {
      if (!(char in node)) return false;
      node = node.children.get(char);
    }
    return true;
  }
 
  getWordsWithPrefix(prefix: string): string[] {
    let node = this.root;
    for (const char of prefix) {
      if (!(char in node)) return [];
      node = node[char];
    }
 
    const results = [];
    const dfs = (current, path) => {
      if (current['*']) results.push(path);
 
      for (const key in current) {
        if (key !== '*') dfs(curreny[key], path + key);
      }
    };
 
    dfs(node, prefix);
    return results;
  }
 
  delete(word: string): boolean {
    let node = this.root;
    for (const char of word) {
      if (!(char in node)) return false;
      node = node[char];
    }
 
    if (!('*' in node)) return false
 
    node['*'] = false
    
    return true
  }
 
  // inputs:
  // -> 'car'
  // -> 'c.r'
  isWordInTrie(pattern: string): boolean {
 
    const dfs = (node, i) => {
      if (i === pattern.length) {
        return !!node['*']; // reached end of pattern
      }
 
      const char = pattern[i];
 
      // Wildcard case: try all possible children
      if (char === '.') {
        for (const key in node) {
          if (key === '*') continue; // skip word-end marker
          if (dfs(node[key], i + 1)) return true;
        }
        return false;
      }
 
      // Normal character match
      if (!(char in node)) return false;
      return dfs(node[char], i + 1);
    };
 
    return dfs(this.root, 0);
  }
}

LinkIconTime Complexity

OperationWorstDescription
InsertO(L)L = length of word
SearchO(L)L = length of word
Prefix SearchO(L)L = length of word
InsertO(L)L = length of word
isWordInTrieO(∑^w * L)∑ = alphabet 26 characters,
w = wildcards,
L = length of word