Insert Word in Trie

Contents

ProblemExamplesVisualizationSolutionAlgorithmCode

Problem Statement❯

Given a Trie (prefix tree), insert a word into it. A Trie is used to efficiently store and retrieve strings, especially useful for prefix-based searches. The objective is to add the given word into the Trie character by character such that each character leads to a node, and the final character marks the end of the word.

Examples❯

Case Input Trie Word to Insert Expected Result
Normal Case Trie with 'cat', 'car'.
'cart' Adds 't' after 'car' branch and mark 't' as end of word. Visualization
Prefix Exists Trie with 'apple'
'app' 'app' already exists as a prefix. Mark 'p' as end of word; no need to add new nodes. Visualization
Empty Trie Empty
'dog' Creates a new path: 'd' → 'o' → 'g' Visualization
Empty Word Trie with 'cat'
'' No changes; nothing is inserted Visualization
Word Already Exists Trie with 'hello'
'hello' Since the word already exists, nothing has to be done to the trie. Visualization

Visualization Player

Solution❯

To insert a word into a Trie, we follow a step-by-step character-wise traversal:

  • Case 1: Normal Case

    1. Suppose the Trie already contains some words like 'cat' and 'car'.
    2. When we try to insert 'cart', we follow the path 'c' → 'a' → 'r'.
    3. Since 'r' exists, we don't create it again. Now we see 't' is not present as a child of 'r', so we create a new node for 't'.
    4. And mark 't' as the end of the word.

  • Case 2: Prefix Exists

    1. If the Trie already has 'apple' and we want to insert 'app'
    2. we follow 'a' → 'p' → 'p'. Since these nodes already exist, we don’t need to create them again.
    3. But since 'app' ends here, we mark the current 'p' as the end of a valid word (it may not have been marked earlier).

  • Case 3: Empty Trie

    1. When inserting into an empty Trie (i.e., it has only the root node), we create a new child node for each character in the word. For 'dog',
    2. we create 'd',
    3. then 'o',
    4. then 'g',
    5. marking 'g' as the end of the word.
  • Case 4: Empty Word – If the input word is an empty string, there’s nothing to insert. No operation is performed, and the Trie remains unchanged.
  • Case 5: Word Already Exists – If the word to insert is already in the Trie, the traversal simply follows the existing path. We just ensure that the last character is marked as the end of a valid word. This helps if the word was previously just a prefix and not marked as a complete word.

Algorithm Steps❯

  1. Initialize a pointer to the root node of the Trie.
  2. Iterate through each character of the input word:
    1. If the character does not exist in the current node's children, create a new node for it.
    2. Move the pointer to this child node.
  3. After processing all characters, mark the last node as the end of a valid word.

Code

JavaScript
class TrieNode {
  constructor() {
    this.children = {};
    this.is_end_of_word = false;
  }
}

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

  insert(word) {
    let node = this.root;
    for (let char of word) {
      if (!node.children[char]) {
        node.children[char] = new TrieNode();
      }
      node = node.children[char];
    }
    node.is_end_of_word = true;
  }
}

// Example usage:
const trie = new Trie();
trie.insert("code");
trie.insert("coder");
trie.insert("coding");
console.log(JSON.stringify(trie, null, 2));