05_01_2025.md

Course	By	Link
The Last Algorithms Course You'll Need	The Primeagen	https://frontendmasters.com/courses/algorithms/

Tries (Trie Tree)

My implementation:

class TrieNode {
    isWord: boolean;
    children: Record<string, TrieNode>;

    constructor() {
        this.isWord = false;
        this.children = {};
    }
}

export default class Trie {
    private root: TrieNode;

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

    insert(item: string): void {
        let node = this.root;

        for (let c of item) {
            if (!node.children[c]) {
                node.children[c] = new TrieNode();
            }

            node = node.children[c];
        }

        node.isWord = true;
    }

    delete(item: string): void {
        const dfs = (
            node: TrieNode | undefined,
            item: string,
            index: number,
        ): boolean => {
            // base case
            // 1. out of trie
            if (!node) {
                return false;
            }

            // 2. end of word
            if (index === item.length) {
                if (!node.isWord) {
                    return false;
                }

                node.isWord = false;

                if (Object.keys(node.children).length) {
                    return false;
                }

                return true;
            }

            // recursion
            // pre
            // get character
            const char = item[index];

            // recurse
            const canDelete = dfs(node.children[char], item, index + 1);

            // post
            if (canDelete) {
                delete node.children[char];

                return !Object.keys(node.children).length && !node.isWord;
            }

            return false;
        };

        dfs(this.root, item, 0);
    }

    find(partial: string): string[] {
        const result: string[] = [];
        let node = this.root;

        for (let c of partial) {
            if (!node.children[c]) {
                return [];
            }

            node = node.children[c];
        }

        const dfs = (node: TrieNode, prefix: string): void => {
            if (node.isWord) {
                result.push(prefix);
            }

            for (const c in node.children) {
                dfs(node.children[c], prefix + c);
            }
        };

        dfs(node, partial);

        return result;
    }
}

Notes

• find from prefix function that require to return all words that start with the given prefix, need to use DFS to traverse the trie tree and collect all words that are marked as isWord.
• delete function should be implemented as a recursive function because we need to delete the nodes from the bottom up.
• delete function has some tricks that need to be handled:
  • If we have "apple" and "app" in the trie, and we want to delete "app", we should not delete the "p" node because it is shared between "apple" and "app". In this case, we should only mark the "app" node as not a word. If we delete the "p" node, we will lose the "apple" word.
  • If we have "apple" and "apples" in the trie, and we want to delete "apples", in this case we can delete the "s" because it has no children below it. But we should not delete the "e" node because it currently marks a word "apple". Meaning we should only delete when the node has no children and it is not a word, until we reach a node that has children or marks a word. This is why we need to return a boolean from the recursive function to indicate if we should delete the current node or not.