Insert Word in Trie

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.

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 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.

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.

#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;
}

#include <iostream>
#include <unordered_map>
using namespace std;

class TrieNode {
public:
    unordered_map<char, TrieNode*> children;
    bool is_end_of_word = false;
};

class Trie {
    TrieNode *root;
public:
    Trie() { root = new TrieNode(); }

    void insert(const string &word) {
        TrieNode *node = root;
        for (char c : word) {
            if (!node->children[c]) node->children[c] = new TrieNode();
            node = node->children[c];
        }
        node->is_end_of_word = true;
    }
};

int main() {
    Trie trie;
    trie.insert("code");
    trie.insert("coder");
    trie.insert("coding");
    cout << "Inserted words into Trie" << endl;
    return 0;
}

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end_of_word = False

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_end_of_word = True

# Example usage:
trie = Trie()
trie.insert("code")
trie.insert("coder")
trie.insert("coding")
print("Inserted words into Trie")

import java.util.HashMap;

class TrieNode {
    HashMap<Character, TrieNode> children = new HashMap<>();
    boolean isEndOfWord = false;
}

public class Trie {
    private TrieNode root;

    public Trie() {
        root = new TrieNode();
    }

    public void insert(String word) {
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            node.children.putIfAbsent(c, new TrieNode());
            node = node.children.get(c);
        }
        node.isEndOfWord = true;
    }

    public static void main(String[] args) {
        Trie trie = new Trie();
        trie.insert("code");
        trie.insert("coder");
        trie.insert("coding");
        System.out.println("Inserted words into Trie");
    }
}

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("Inserted words into Trie");

package main

import "fmt"

const CharSize = 26

type TrieNode struct {
    children [CharSize]*TrieNode
    isEndOfWord bool
}

type Trie struct {
    root *TrieNode
}

func NewTrieNode() *TrieNode {
    return &TrieNode{}
}

func NewTrie() *Trie {
    return &Trie{root: NewTrieNode()}
}

func (t *Trie) Insert(word string) {
    node := t.root
    for _, ch := range word {
        index := ch - 'a'
        if node.children[index] == nil {
            node.children[index] = NewTrieNode()
        }
        node = node.children[index]
    }
    node.isEndOfWord = true
}

func main() {
    trie := NewTrie()
    trie.Insert("code")
    trie.Insert("coder")
    trie.Insert("coding")
    fmt.Println("Inserted words into Trie")
}

use std::collections::HashMap;

struct TrieNode {
    children: HashMap<char, TrieNode>,
    is_end_of_word: bool,
}

impl TrieNode {
    fn new() -> Self {
        TrieNode {
            children: HashMap::new(),
            is_end_of_word: false,
        }
    }
}

struct Trie {
    root: TrieNode,
}

impl Trie {
    fn new() -> Self {
        Trie { root: TrieNode::new() }
    }

    fn insert(&mut self, word: &str) {
        let mut node = &mut self.root;
        for ch in word.chars() {
            node = node.children.entry(ch).or_insert_with(TrieNode::new);
        }
        node.is_end_of_word = true;
    }
}

fn main() {
    let mut trie = Trie::new();
    trie.insert("code");
    trie.insert("coder");
    trie.insert("coding");
    println!("Inserted words into Trie");
}

class TrieNode {
    val children = mutableMapOf<Char, TrieNode>()
    var isEndOfWord = false
}

class Trie {
    private val root = TrieNode()

    fun insert(word: String) {
        var node = root
        for (char in word) {
            node = node.children.getOrPut(char) { TrieNode() }
        }
        node.isEndOfWord = true
    }
}

fun main() {
    val trie = Trie()
    trie.insert("code")
    trie.insert("coder")
    trie.insert("coding")
    println("Inserted words into Trie")
}

class TrieNode {
    var children: [Character: TrieNode] = [:]
    var isEndOfWord = false
}

class Trie {
    private let root = TrieNode()

    func insert(_ word: String) {
        var node = root
        for char in word {
            if node.children[char] == nil {
                node.children[char] = TrieNode()
            }
            node = node.children[char]!
        }
        node.isEndOfWord = true
    }
}

let trie = Trie()
trie.insert("code")
trie.insert("coder")
trie.insert("coding")
print("Inserted words into Trie")

class TrieNode {
  children: { [key: string]: TrieNode } = {};
  isEndOfWord: boolean = false;
}

class Trie {
  root: TrieNode;

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

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

// Example usage:
const trie = new Trie();
trie.insert("code");
trie.insert("coder");
trie.insert("coding");
console.log("Inserted words into Trie");

Time complexity

Space complexity

O(n)

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.