Trie Insert Operation in DSA Javascript

Mental Model

A trie stores words by sharing common prefixes in a tree structure, adding new letters as branches.

Analogy: Imagine a tree of roads where each letter is a street sign; inserting a word means building new streets only where needed.

root
 ↓
 {}  (empty root node with no children)

Dry Run Walkthrough

Input: Insert words: 'cat', then 'car'

Goal: Build a trie that stores both words sharing the prefix 'ca'

Step 1: Insert 'c' from 'cat' at root

root
 ↓
 {c: {}}

Why: Start the branch for the first letter 'c'

Step 2: Insert 'a' after 'c'

root
 ↓
 {c: {a: {}}}

Why: Add next letter 'a' as child of 'c'

Step 3: Insert 't' after 'a' and mark end of word

root
 ↓
 {c: {a: {t: {end: true}}}}

Why: Complete word 'cat' by adding 't' and marking word end

Step 4: Insert 'c' from 'car' (already exists)

root
 ↓
 {c: {a: {t: {end: true}}}}

Why: Reuse existing 'c' node for new word

Step 5: Insert 'a' after 'c' (already exists)

root
 ↓
 {c: {a: {t: {end: true}}}}

Why: Reuse existing 'a' node for new word

Step 6: Insert 'r' after 'a' and mark end of word

root
 ↓
 {c: {a: {t: {end: true}, r: {end: true}}}}

Why: Add new branch 'r' to complete 'car'

Result:

root
 ↓
 {c: {a: {t: {end: true}, r: {end: true}}}}

Annotated Code

DSA Javascript

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

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

  insert(word) {
    let node = this.root;
    for (const char of word) {
      if (!node.children[char]) {
        node.children[char] = new TrieNode();
      }
      node = node.children[char]; // advance to child node
    }
    node.end = true; // mark end of word
  }

  print(node = this.root, prefix = '') {
    if (node.end) {
      console.log(prefix);
    }
    for (const char in node.children) {
      this.print(node.children[char], prefix + char);
    }
  }
}

const trie = new Trie();
trie.insert('cat');
trie.insert('car');
trie.print();

for (const char of word) {

iterate over each letter in the word

if (!node.children[char]) {

check if current letter branch exists

node.children[char] = new TrieNode();

create new node if branch missing

node = node.children[char]; // advance to child node

move down to the child node for next letter

node.end = true; // mark end of word

mark current node as end of a valid word

Output

cat

car

Complexity Analysis

Time: O(m) because we process each of the m letters in the word once

Space: O(m) in worst case when all letters are new and need new nodes

vs Alternative: Compared to storing words in a list, trie insert is faster for prefix queries but uses more space

Edge Cases

Inserting empty string

Marks root as end of word without adding children

DSA Javascript

node.end = true; // mark end of word

Inserting word already in trie

No new nodes created, just marks end again

DSA Javascript

if (!node.children[char]) {

Inserting word with shared prefix

Reuses existing nodes for prefix, adds new nodes only for suffix

DSA Javascript

if (!node.children[char]) {

When to Use This Pattern

When you need to store many words and quickly check prefixes, use a trie insert pattern to build a prefix tree efficiently.

Common Mistakes

Mistake: Not marking the end of word node, so words are not recognized as complete
Fix: Always set node.end = true after inserting all letters

Mistake: Overwriting existing child nodes instead of checking if they exist
Fix: Check if child exists before creating new node

Summary

Inserts words letter by letter into a tree structure sharing prefixes.

Use when you want fast prefix-based word storage and lookup.

The key is to reuse existing nodes for shared prefixes and mark word ends.