Insert Word in Trie - Visualization

Tries

Contents

VisualizationProblemExamplesSolutionAlgorithmCodeTimeSpace

Visualization Player

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

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

C
C++
Python
Java
JS
Go
Rust
Kotlin
Swift
TS
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define CHAR_SIZE 26

typedef struct TrieNode {
    struct TrieNode *children[CHAR_SIZE];
    bool is_end_of_word;
} TrieNode;

TrieNode* createNode() {
    TrieNode *node = (TrieNode*)malloc(sizeof(TrieNode));
    node->is_end_of_word = false;
    for (int i = 0; i < CHAR_SIZE; i++) node->children[i] = NULL;
    return node;
}

void insert(TrieNode *root, const char *word) {
    TrieNode *node = root;
    while (*word) {
        int index = *word - 'a';
        if (!node->children[index]) node->children[index] = createNode();
        node = node->children[index];
        word++;
    }
    node->is_end_of_word = true;
}

int main() {
    TrieNode *root = createNode();
    insert(root, "code");
    insert(root, "coder");
    insert(root, "coding");
    printf("Inserted words into Trie\n");
    return 0;
}

Time Complexity❯

CaseTime ComplexityExplanation
Best CaseO(n)In the best case, the algorithm still needs to traverse all n characters of the input word to insert it into the Trie, even if all nodes already exist.
Average CaseO(n)On average, the algorithm traverses and possibly creates n new nodes for a word of length n. Each character requires a constant-time operation.
Worst CaseO(n)In the worst case, none of the characters exist in the Trie, so the algorithm creates a new node for each of the n characters in the input word.

Space Complexity❯

O(n)

Explanation: In the worst case, the algorithm adds n new nodes for a word of length n, resulting in linear space usage. No additional auxiliary space is used.


Comments

💬 Please keep your comment relevant and respectful. Avoid spamming, offensive language, or posting promotional/backlink content.
All comments are subject to moderation before being published.

Loading comments...