DEV Community

keshav Sandhu
keshav Sandhu

Posted on

1

Introduction to Trie (Prefix Tree)

A Trie is a tree-like data structure that is used for efficiently storing and searching strings, especially in applications like autocomplete, spell checking, and IP routing.


Key Properties of a Trie:

  1. Nodes: Each node represents a character.
  2. Root: The root node is empty and serves as the starting point.
  3. Children: Each node has up to 26 children (for lowercase English letters) or more, depending on the character set.
  4. End-of-Word Marker: Some nodes are marked to indicate the end of a word.

Basic Trie Operations:

1. Insertion

Inserting a word involves traversing the trie and creating new nodes for characters that don’t exist.

2. Search

Search checks whether a word exists in the trie by traversing its nodes.

3. Prefix Search

This checks whether any word in the trie starts with a given prefix.


Implementation of Basic Trie in JavaScript:

class TrieNode {
    constructor() {
        this.children = {}; // Stores child nodes
        this.isEndOfWord = false; // Marks the end of a word
    }
}

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

    // Insert a word
    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.isEndOfWord = true; // Mark the end of the word
    }

    // Search for a word
    search(word) {
        let node = this.root;
        for (let char of word) {
            if (!node.children[char]) {
                return false;
            }
            node = node.children[char];
        }
        return node.isEndOfWord;
    }

    // Check if any word starts with the given prefix
    startsWith(prefix) {
        let node = this.root;
        for (let char of prefix) {
            if (!node.children[char]) {
                return false;
            }
            node = node.children[char];
        }
        return true;
    }
}

// Example usage
const trie = new Trie();
trie.insert("apple");
console.log(trie.search("apple"));   // true
console.log(trie.search("app"));     // false
console.log(trie.startsWith("app")); // true
trie.insert("app");
console.log(trie.search("app"));     // true
Enter fullscreen mode Exit fullscreen mode

Advanced Trie Operations:

1. Delete a Word:

Deleting a word involves a recursive approach, where we remove nodes that are no longer needed.

delete(word, node = this.root, depth = 0) {
    if (depth === word.length) {
        if (!node.isEndOfWord) return false; // Word doesn't exist
        node.isEndOfWord = false;
        return Object.keys(node.children).length === 0; // Check if node has children
    }

    const char = word[depth];
    if (!node.children[char]) return false;

    const shouldDeleteChild = this.delete(word, node.children[char], depth + 1);

    if (shouldDeleteChild) {
        delete node.children[char];
        return Object.keys(node.children).length === 0 && !node.isEndOfWord;
    }

    return false;
}
Enter fullscreen mode Exit fullscreen mode

2. Count Words with a Prefix:

Count how many words start with a given prefix.

countWordsWithPrefix(prefix) {
    let node = this.root;
    for (let char of prefix) {
        if (!node.children[char]) return 0;
        node = node.children[char];
    }
    return this._countWords(node);
}

_countWords(node) {
    let count = node.isEndOfWord ? 1 : 0;
    for (let char in node.children) {
        count += this._countWords(node.children[char]);
    }
    return count;
}
Enter fullscreen mode Exit fullscreen mode

3. Autocomplete Suggestions:

Given a prefix, return all words that start with it.

getWordsWithPrefix(prefix) {
    let node = this.root;
    for (let char of prefix) {
        if (!node.children[char]) return [];
        node = node.children[char];
    }
    return this._collectWords(node, prefix);
}

_collectWords(node, prefix) {
    let results = [];
    if (node.isEndOfWord) results.push(prefix);

    for (let char in node.children) {
        results = results.concat(this._collectWords(node.children[char], prefix + char));
    }

    return results;
}
Enter fullscreen mode Exit fullscreen mode

Time Complexity:

  1. Insert: O(L) (L = length of the word)
  2. Search: O(L)
  3. Prefix Search: O(L)
  4. Delete: O(L)

Applications of Trie:

  1. Autocomplete Systems (e.g., search bars, text editors).
  2. Spell Checkers.
  3. IP Routing (longest prefix matching).
  4. Word Games (e.g., Boggle).
  5. DNA Sequence Matching.
👋 Kindness is contagious

Please leave your appreciation by commenting on this post!

It takes one minute and is worth it for your career.

Get started

Thank you in advance!

Top comments (0)

A Workflow Copilot. Tailored to You.

Pieces.app image

Our desktop app, with its intelligent copilot, streamlines coding by generating snippets, extracting code from screenshots, and accelerating problem-solving.

Read the docs

👋 Kindness is contagious

Immerse yourself in a wealth of knowledge with this piece, supported by the inclusive DEV Community—every developer, no matter where they are in their journey, is invited to contribute to our collective wisdom.

A simple “thank you” goes a long way—express your gratitude below in the comments!

Gathering insights enriches our journey on DEV and fortifies our community ties. Did you find this article valuable? Taking a moment to thank the author can have a significant impact.

Okay