Implement Trie Prefix Tree - JS Solution

Editorial

Editorial solutions and visualizations are prepared with care, but we do not guarantee 100% accuracy or completeness. Please use your own judgment to verify results. Visucodize is not responsible for decisions made based on this content.

const CURRENT = 'current', CURRENT_COLOR = 'blue';
const FOUND = 'found', FOUND_COLOR = 'green';
const NOT_COMPLETE_WORD = 'not_complete_word', NOT_COMPLETE_WORD_COLOR = 'red';

class TrieNode {
    constructor() {
        this.children = new VisChildrenObject();
        this.endOfTheWord = false;
    }
}

class Trie {
    constructor() {
        this.root = new TrieNode();
        this.tree = new VisDictionaryTree(this.root, {
            dataPropName: 'endOfTheWord',
        }).options({
            labelExtractionPolicy: d => (d === true ? 'END' : ''),
        }).createVis();
    }

    insert(word) {
        let node = this.root;

        startPartialBatch();
        const wordVis = new VisArray(...word).options({ label: 'word' });
        let index = 0;
        makeVisVariable(index).registerAsIndexPointer(wordVis, CURRENT);
        setCurrentNode(node, this.tree);
        notification(`✏️ Inserting word <b>${word}</b> into the Trie.`);
        endBatch();

        for (const char of word) {
            startPartialBatch();
            if (!node.children[char]) {
                notification(`➕ No child for <b>${char}</b> found at ${makeColoredSpan('current node', CURRENT_COLOR)}. Creating new node for <b>${char}</b> and proceeding to it.`);
                node.children[char] = new TrieNode();
            } else {
                notification(`➡️ Child node for <b>${char}</b> exists at ${makeColoredSpan('current node', CURRENT_COLOR)}. Proceeding from ${makeColoredSpan('current node', CURRENT_COLOR)} to it.`);
            }
            node = node.children[char];
            setCurrentNode(node, this.tree);
            index += 1;
            endBatch();
        }

        startPartialBatch();
        notification(`✅ All characters inserted. Marking ${makeColoredSpan('current node', CURRENT_COLOR)} as ${makeColoredSpan('end of word', FOUND_COLOR)}.`);
        node.endOfTheWord = true;
        endBatch();
    }

    search(word) {
        notification(`🔍 <b>Searching</b> for "<b>${word}</b>": the path must exist <i>and</i> the final node must be marked as ${makeColoredSpan('end of word', FOUND_COLOR)}.`);
        const node = this._traverse(word);

        if (node && node.endOfTheWord) {
            toggleClassWithNotification(node, this.tree, FOUND, `✅ Word <b>${word}</b> exists in the Trie.`);
            return true;
        } else if (node) {
            toggleClassWithNotification(node, this.tree, NOT_COMPLETE_WORD, `❌ <b>Not a complete word:</b> A path for <b>${word}</b> exists but ${makeColoredSpan('current node', CURRENT_COLOR)} isn't marked as ${makeColoredSpan('end of word', FOUND_COLOR)}.`);
            return false;
        }
        return false; // No need for extra notification here (_traverse handles it)
    }

    startsWith(prefix) {
        notification(`🔍 <b>Checking prefix</b> "<b>${prefix}</b>": we only need the path to exist — no ${makeColoredSpan('end of word', FOUND_COLOR)} required.`);
        const node = this._traverse(prefix);

        if (node) {
            toggleClassWithNotification(node, this.tree, FOUND, `✅ At least one word starts with <b>${prefix}</b>.`);
            return true;
        }
        return false; // _traverse already notifies if prefix breaks
    }

    _traverse(path) {
        let node = this.root;

        startPartialBatch();
        const pathVis = new VisArray(...path).options({ label: 'path' });
        let index = 0;
        makeVisVariable(index).registerAsIndexPointer(pathVis, CURRENT);
        setCurrentNode(node, this.tree);
        notification(`🧭 Traversing for "<b>${path}</b>": following each character starting from the ${makeColoredSpan('root', CURRENT_COLOR)}.`);
        endBatch();

        for (const char of path) {
            startPartialBatch();
            if (!node.children[char]) {
                notification(`❌ <b>Path not found:</b> No child for <b>${char}</b> at ${makeColoredSpan('current node', CURRENT_COLOR)}.`);
                pathVis.destroyVis();
                endBatch();
                return null;
            }
            notification(`➡️ Moving from ${makeColoredSpan('current node', CURRENT_COLOR)} to its child node for <b>${char}</b>.`);
            node = node.children[char];
            setCurrentNode(node, this.tree);
            index += 1;
            endBatch();
        }

        pathVis.destroyVis();
        return node;
    }
}

function visMainFunction(operations, args) {
    initClassProperties();
    explanationAndColorSchemaNotifications();

    let trie = null;
    const results = [];

    for (let i = 0; i < operations.length; i++) {
        const op = operations[i];
        const arg = args[i][0]; // single argument per op
        if (op === 'Trie') {
            notification(`🚀 Initializing the Trie.`);
            trie = new Trie();
            results.push(null);
        } else if (op === 'insert') {
            trie.insert(arg);
            results.push(null);
        } else if (op === 'search') {
            const res = trie.search(arg);
            results.push(res);
        } else if (op === 'startsWith') {
            const res = trie.startsWith(arg);
            results.push(res);
        }
    }
    return results;
}

// --- Visual helpers ---

let currentNode = null;

function toggleClassWithNotification(node, tree, className, message) {
    startPartialBatch();
    const vm = tree.makeVisManagerForNode(node);
    vm.addClass(className);
    notification(message);
    vm.removeClass(className);
    endBatch();
}

function setCurrentNode(node, tree) {
    if (node === currentNode) return;
    startBatch();
    currentNode && tree.makeVisManagerForNode(currentNode).removeClass(CURRENT);
    node && tree.makeVisManagerForNode(node).addClass(CURRENT);
    currentNode = node;
    endBatch();
}

function initClassProperties() {
    setClassProperties(CURRENT, { borderColor: CURRENT_COLOR });
    setClassProperties(FOUND, { backgroundColor: FOUND_COLOR });
    setClassProperties(NOT_COMPLETE_WORD, { backgroundColor: NOT_COMPLETE_WORD_COLOR });
}

function explanationAndColorSchemaNotifications() {
  explanationNotification();
  notification(`
    <b>🎨 Visual Cues (Color Schema)</b>
    <ul>
      <li>${makeColoredSpan('Current', CURRENT_COLOR)} — ${CURRENT_COLOR} border for the current <b>character</b> being processed or the corresponding <b>Trie node</b> during traversal or insertion.</li>
      <li>${makeColoredSpan('Found node', FOUND_COLOR)} — ${FOUND_COLOR} background when a word or prefix is successfully found.</li>
      <li>${makeColoredSpan('Not a complete word', NOT_COMPLETE_WORD_COLOR)} — ${NOT_COMPLETE_WORD_COLOR} background when the path exists but the final node is not marked as a complete word.</li>
    </ul>
  `);
}

Approach

A Trie stores strings character by character along root→leaf paths. Each node holds a map of children (next characters) and a boolean flag endOfTheWord that marks the completion of a valid word. During insertion, if a child for a character already exists, it is reused instead of recreated — ensuring that common prefixes are shared and traversal simply follows existing paths from the root.

🔧 Operations

insert(word): Walk from the root over the characters of word. If a child for the current character doesn’t exist, create it. After the last character, set endOfTheWord = true.
search(word): Traverse the path for all characters of word. If at any step a child is missing, return false. Otherwise, return true only if the final node has endOfTheWord = true.
startsWith(prefix): Traverse the path for all characters of prefix. If any child is missing, return false; if the full path exists, return true (no need for endOfTheWord).

🧠 Correctness Intuition

Because all words sharing a prefix converge to the same node reached by that prefix, verifying a prefix is just checking the existence of a path from the root. Verifying a whole word additionally requires the terminal node to be marked with endOfTheWord.

⏱️ Complexity

Let L be the length of the input string (word or prefix).
Time: O(L) for insert, search, and startsWith (one step per character).
Space: Up to O(totalCharacters) across all inserted words (each distinct edge/node created at most once).

Time Complexity

Let L be the length of the input string (word or prefix).
Each operation — insert, search, and startsWith — runs in O(L) time, since at most one node is visited (and in some cases created as well) per character.

Space Complexity

Let L be the input word length, and M be the total number of characters across all inserted words.

Per insert (single word of length L): O(L). At most L new nodes are created — the worst case occurs when no existing prefix is already available in the Trie. The endOfTheWord flag adds O(1), which does not affect the overall complexity.
Building the whole Trie (all words): O(M). At most M nodes are created — the worst case occurs when no shared prefixes exist.

Input-1

Implement Trie Prefix Tree - JS Solution

Solution code

Solution explanation

Solution explanation

Approach

🔧 Operations

🧠 Correctness Intuition

⏱️ Complexity

Time Complexity

Space Complexity