Trie Implementation

Implement a trie from scratch using a TrieNode class whose children are stored in a Map, then add insert, search, and startsWith methods that all run in O(m) time.

5 min read Level 3/5 #dsa#trie#implementation

What you'll learn

Implement a TrieNode class with a children Map and an isEnd flag
Write insert, search, and startsWith on a Trie class
Trace through an insertion and lookup to verify correctness

Every trie starts with an empty root node. As words are inserted, character-keyed children are created on demand. A Map is the natural choice for children in JavaScript: keys are arbitrary characters, lookups are O(1) average, and iteration order is insertion order.

The TrieNode Class

class TrieNode {
  constructor() {
    this.children = new Map(); // char → TrieNode
    this.isEnd = false;        // true when a complete word ends here
  }
}

isEnd is what distinguishes “cat” from the prefix “ca” when both are stored. Without it, searching for “ca” would succeed even if you only inserted “cat”.

The Trie Class

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

  /** Insert a word into the trie. O(m) */
  insert(word) {
    let node = this.root;
    for (const char of word) {
      if (!node.children.has(char)) {
        node.children.set(char, new TrieNode());
      }
      node = node.children.get(char);
    }
    node.isEnd = true;
  }

  /** Return true if word exists exactly. O(m) */
  search(word) {
    const node = this._traverse(word);
    return node !== null && node.isEnd;
  }

  /** Return true if any stored word starts with prefix. O(m) */
  startsWith(prefix) {
    return this._traverse(prefix) !== null;
  }

  /** Walk the trie along the characters of s; return final node or null. */
  _traverse(s) {
    let node = this.root;
    for (const char of s) {
      if (!node.children.has(char)) return null;
      node = node.children.get(char);
    }
    return node;
  }
}

_traverse is extracted so that search and startsWith share the same walk logic; they differ only in what they check on the returned node.

Tracing an Example

const trie = new Trie();
trie.insert("cat");
trie.insert("car");
trie.insert("card");

trie.search("car");      // true  — isEnd is set on the 'r' node
trie.search("ca");       // false — isEnd is not set on the 'a' node
trie.startsWith("ca");   // true  — the 'a' node exists
trie.startsWith("dog");  // false — no 'd' child on root

After these three inserts the trie looks like:

root
 └── c
      └── a
           ├── t (isEnd)
           └── r (isEnd)
                └── d (isEnd)

Complexity

Method	Time	Extra Space
insert(word)	O(m)	O(m) new nodes worst case
search(word)	O(m)	O(1)
startsWith(prefix)	O(m)	O(1)

m is the length of the input string. None of the methods depend on how many words are already stored, which is the key advantage over linear scan.

Handling Deletions

Deletion is optional for interview problems, but useful in practice. Walk to the end of the word, clear isEnd, then prune any leaf nodes on the way back up using a recursive helper. The walk is still O(m).

Up Next

Use the _traverse helper to collect all words that share a given prefix — the foundation of an autocomplete engine.

Autocomplete with Tries →