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.

Top comments (0)

Billboard image

The Next Generation Developer Platform

Coherence is the first Platform-as-a-Service you can control. Unlike "black-box" platforms that are opinionated about the infra you can deploy, Coherence is powered by CNC, the open-source IaC framework, which offers limitless customization.

Learn more

๐Ÿ‘‹ Kindness is contagious

Please leave a โค๏ธ or a friendly comment on this post if you found it helpful!

Okay