Trie Insert, Search and Delete Operations Tutorial

Trie Core Operations

The three fundamental operations in a Trie are insertion, search, and deletion. All three operations work by following a path of characters from the root.

Unlike a structure that stores complete strings as individual values, a Trie shares nodes when multiple words have the same prefix. This makes prefix-based operations especially natural.

Words:

car
care
cat

Trie:

(root)
  |
  c
  |
  a
 /|\
r t
|
e

* = end of word

The End-of-Word Marker

A Trie node needs to know whether it represents the end of a complete word. This is usually stored using a Boolean property such as isEndOfWord.

This becomes important when one word is also a prefix of another word.

car
care

c → a → r → e
        *
        |
        r is the end of "car"
        e is the end of "care"

If the r node is not marked as an end of a word, the Trie would know that car is a character path but would not know whether car was actually inserted.

1. Inserting a Word

Insertion processes the word one character at a time. Starting from the root, the implementation checks whether a child exists for the current character.

If the child exists, follow it.
If the child does not exist, create a new node.
Continue until every character has been processed.
Mark the final node as the end of a complete word.

Insertion Example

Consider inserting cat into an empty Trie.

Start:

(root)

Insert 'c':

(root)
  |
  c

Insert 'a':

(root)
  |
  c
  |
  a

Insert 't':

(root)
  |
  c
  |
  a
  |
  t *

* = end of word

JavaScript Implementation

insert(word) {
  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;
}

Inserting Words With a Shared Prefix

One of the main characteristics of a Trie is that common prefixes share the same nodes. Suppose we insert car and then cat.

After inserting "car":

(root)
  |
  c
  |
  a
  |
  r *


After inserting "cat":

(root)
  |
  c
  |
  a
 / \
r   t
*   *

The nodes for c and a are reused. Only the missing t node needs to be created.

2. Searching for a Word

Searching for a complete word follows its character path from the root. The operation succeeds only when every character exists and the final node is marked as an end of a word.

search(word) {
  let current = this.root;

  for (const char of word) {
    if (!current.children.has(char)) {
      return false;
    }

    current = current.children.get(char);
  }

  return current.isEndOfWord;
}

Successful Search

Suppose the Trie contains cat. Searching for cat follows all three character nodes and reaches a node where isEndOfWord is true.

Search "cat"

root
 ↓
 c   found
 ↓
 a   found
 ↓
 t   found
 ↓
isEndOfWord = true

Result: true

Failed Search

If any character is missing, the search can immediately return false.

Stored:
cat

Search:
can

root → c → a → n

'n' does not exist.

Result: false

Prefix vs Complete Word

A character path existing in a Trie does not necessarily mean that the corresponding string is a stored word.

For example, suppose only apple has been inserted:

a → p → p → l → e *

"app" exists as a path.
"app" is not necessarily a stored word.

Therefore:

search("app")      → false
startsWith("app")  → true

3. Deleting a Word

Trie deletion is more complicated than insertion and search because nodes can be shared by multiple words.

The deletion algorithm must remove only the nodes that are no longer needed. It must not destroy a prefix that belongs to another stored word.

Simple Case

Suppose the Trie contains only cat.

Before deletion:

(root)
  |
  c
  |
  a
  |
  t *

Delete "cat":

All nodes on the path become unnecessary
and can be removed.

Shared Prefix Case

Now consider a Trie containing both car and care.

c → a → r * → e *

Delete "car"

Do NOT remove:
c
a
r

Why?

They are still required for "care".

Only:
r.isEndOfWord = false

The r node remains because it has a child representing e.

When Can a Node Be Removed?

A Trie node can generally be removed when both conditions are true:

It is not the end of another stored word.
It has no children.

Node can be removed when:

isEndOfWord = false
children.size = 0

This rule allows deletion to clean up unused nodes while preserving paths shared by other words.

Recursive Deletion

A convenient way to implement Trie deletion is to recursively travel to the end of the target word and then decide whether each node should be removed while returning toward the root.

delete(word) {
  const remove = (node, index) => {
    if (index === word.length) {
      if (!node.isEndOfWord) {
        return false;
      }

      node.isEndOfWord = false;

      return node.children.size === 0;
    }

    const char = word[index];
    const child = node.children.get(char);

    if (!child) {
      return false;
    }

    const shouldDeleteChild = remove(child, index + 1);

    if (shouldDeleteChild) {
      node.children.delete(char);
    }

    return node.children.size === 0 && !node.isEndOfWord;
  };

  remove(this.root, 0);
}

How Recursive Deletion Works

Consider the words car and care. When car is deleted, recursion reaches the node for r. That node is no longer the end of a word, but it still has the child e.

Before:

c → a → r * → e *

Delete "car"

r:
isEndOfWord = false
children = { e }

r must remain.

Result:

c → a → r → e *

If the Trie contained only car, the r node would have no children after its end-of-word flag was cleared, so it could be removed. The cleanup continues backward through a and c if they also become unnecessary.

Complete Trie Implementation

class TrieNode {
  constructor() {
    this.children = new Map();
    this.isEndOfWord = false;
  }
}

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

  insert(word) {
    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) {
    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) {
    let current = this.root;

    for (const char of prefix) {
      if (!current.children.has(char)) {
        return false;
      }

      current = current.children.get(char);
    }

    return true;
  }

  delete(word) {
    const remove = (node, index) => {
      if (index === word.length) {
        if (!node.isEndOfWord) {
          return false;
        }

        node.isEndOfWord = false;

        return node.children.size === 0;
      }

      const char = word[index];
      const child = node.children.get(char);

      if (!child) {
        return false;
      }

      const shouldDeleteChild = remove(child, index + 1);

      if (shouldDeleteChild) {
        node.children.delete(char);
      }

      return node.children.size === 0 &&
             !node.isEndOfWord;
    };

    remove(this.root, 0);
  }
}

Testing Insert, Search, and Delete

A useful test should include exact word searches, missing words, shared prefixes, and deletion of words that overlap with other stored words.

const trie = new Trie();

trie.insert("car");
trie.insert("care");
trie.insert("cat");
trie.insert("dog");

console.log(trie.search("car"));   // true
console.log(trie.search("care"));  // true
console.log(trie.search("can"));   // false

trie.delete("car");

console.log(trie.search("car"));   // false
console.log(trie.search("care"));  // true
console.log(trie.search("cat"));   // true

Operation Complexity

Let L be the length of the word being processed. Each basic operation follows at most one character path from the root.

Operation	Time Complexity	Explanation
Insert	O(L)	Processes each character once
Search	O(L)	Follows the word's character path
Delete	O(L)	Traverses the word and may clean its path
Prefix search	O(L)	Follows the prefix path

These complexities describe the character traversal. The performance of child lookup also depends on the chosen child representation, such as Map or a fixed array.

Memory Considerations

Trie memory usage depends on how many unique character paths are required. Words with many shared prefixes can reuse nodes, while unrelated words may require many separate paths.

Shared prefixes:

apple
application
apply

       a
       |
       p
       |
       p
       |
       l
      / \
     e   i
         |
         c
         |
        ...

Choosing a sparse structure such as Map can help avoid allocating unused child slots.

Important Edge Cases

Inserting the same word multiple times.
Searching for a prefix that is not a complete word.
Deleting a word that does not exist.
Deleting a word that is a prefix of another word.
Deleting a word that shares a prefix with several other words.
Searching an empty string.
Handling uppercase and lowercase characters consistently.

Common Mistakes

Forgetting to set isEndOfWord after insertion.
Returning true from search simply because the character path exists.
Removing shared nodes during deletion.
Deleting a node without checking whether it has children.
Confusing search() with startsWith().
Not handling the case where the word to delete does not exist.
Using inconsistent input normalization.

Key Takeaways

Insertion creates or follows one node for each character.
The final node must be marked as the end of a complete word.
Search requires both a complete character path and an end-of-word marker.
Prefix search only checks whether a character path exists.
Deletion must preserve nodes shared by other words.
A node can usually be removed only when it has no children and is not the end of another word.
Insert, search, prefix search, and delete typically take O(L) time.

Topics

Trie Insert, Search and Delete Operations