Implement Trie (Prefix Tree)

Problem statement

A trie (pronounced as "try") or prefix tree is a tree data structure used to efficiently store and retrieve keys in a dataset of strings. There are various applications of this data structure, such as autocomplete and spellchecker.

Implement the Trie class:

• Trie() Initializes the trie object.
• void insert(String word) Inserts the string word into the trie.
• boolean search(String word) Returns true if the string word is in the trie (i.e., was inserted before), and false otherwise.
• boolean startsWith(String prefix) Returns true if there is a previously inserted string word that has the prefix prefix, and false otherwise.

Example 1:

Input["Trie", "insert", "search", "search", "startsWith", "insert", "search"][[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]Output[null, null, true, false, true, null, true]ExplanationTrie trie = new Trie();trie.insert("apple");trie.search("apple");   // return Truetrie.search("app");     // return Falsetrie.startsWith("app"); // return Truetrie.insert("app");trie.search("app");     // return True

Constraints:

• 1 <= word.length, prefix.length <= 2000
• word and prefix consist only of lowercase English letters.
• At most 3 * 104 calls in total will be made to insert, search, and startsWith.

My solution

class TrieNode {
    constructor(character = null) {
        this.character = character;
        this.isWord = false;
        this.children = {}
        this.parent = null;
    }
    
    
    getWord = () => {
        const output = [];
        
        let node = this;
        
        while(node !== null) {
            output.unshift(node.character);
            node = node.parent;
        }
        
        return output.join("");
    }
    
    
}

/**
 * Initialize your data structure here.
 */
var Trie = function() {
    this.root = new TrieNode(null)
};

/**
 * Inserts a word into the trie. 
 * @param {string} word
 * @return {void}
 */
Trie.prototype.insert = function(word) {
    let currentNode = this.root
    for (let i = 0; i < word.length; i++) {
        const currChar = word.charAt(i);
        
        if (!currentNode.children[currChar]) {
            currentNode.children[currChar] = new TrieNode(currChar);
            currentNode.children[currChar].parent = currentNode;
        }
        
        if (i === word.length - 1) {
            currentNode.children[currChar].isWord = true;
        }
        
        currentNode = currentNode.children[currChar];
    }
};

/**
 * Returns if the word is in the trie. 
 * @param {string} word
 * @return {boolean}
 */
Trie.prototype.search = function(word) {
    let currentNode = this.root;
    
    for (let i = 0; i < word.length; i++) {
        const currChar = word.charAt(i);
        
        if (currentNode.children[currChar]) {
            currentNode = currentNode.children[currChar];
        } else {
            return false;
        }
    }
    
    return currentNode.isWord
};


Trie.prototype.findAllWords = function(node, output) {
    if (!node) {
        return;
    }
    
    if (node.isWord) {
        output.push(node.getWord())
    }
    
    for (const child in node.children) {
        this.findAllWords(node.children[child], output)
    }
}

/**
 * Returns if there is any word in the trie that starts with the given prefix. 
 * @param {string} prefix
 * @return {boolean}
 */
Trie.prototype.startsWith = function(prefix) {
    let currentNode = this.root;
    let output = []
    
    for (let i = 0; i < prefix.length; i++) {
        const currChar = prefix.charAt(i);
        
        if (currentNode.children[currChar]) {
            currentNode = currentNode.children[currChar];
        } else {
            return false;
        }
    }
    
    // this.findAllWords(currentNode, output)
    
    // console.log("output", output)
    
    return true;
};

/** 
 * Your Trie object will be instantiated and called as such:
 * var obj = new Trie()
 * obj.insert(word)
 * var param_2 = obj.search(word)
 * var param_3 = obj.startsWith(prefix)
 */