Trie for bip39

trie.js

// assumes words are all on one line split by spaces
//const words = require("fs").readFileSync("bip39.txt", "utf8").split(" ").sort();
const words = "animal adjective animation build bridge".split(" ").sort()
let trie = {};

for (let i = 0; i < words.length; i++ ) {
    const word = words[i]; 
    const letters = word.split("");
    let pointer = trie; // save pointer for traversal

    // for each letter in this word
	for (let j = 0; j < letters.length; j++ ) {
        const letter = letters[j];
        const subtrie = pointer[letter];

		if (subtrie == null) {
            // if no subtrie, create one
            if (j === letters.length - 1) {
                // end of the word, mark a leaf node
                pointer[letter] = {"_":0};
            } else {
                // create an obejct to traverse into
                pointer[letter] = {};
            }
        }
        pointer = pointer[letter];
	}
}

// traverse the trie down along the prefix and return a pointer to the end location
function traverse(trie, prefix) {
    const letters = prefix.split("");
    let pointer = trie;

    for (let i = 0; i < letters.length; i++) {
        const letter = letters[i];
        if (pointer[letter] === null || pointer[letter] == undefined) {
            return null;
        } 
        pointer = pointer[letter];
    }
    return pointer;
}

// suggest the next letter than can be typed based on a prefix
function suggestLettersFromPrefix(trie, prefix) {
    const pointer = traverse(trie, prefix);
    return pointer === null ? [] : Object.keys(pointer);
}

// suggest words that can be typed based on a prefix
function suggestWordsFromPrefix(trie, prefix) {
    let traversedTrie = traverse(trie, prefix);
    let result = [];

    function helper(word, pointer) {
        for (let letter in pointer) {
            if (letter === "_") {
                result.push(prefix + word);
            } else {
                helper(word + letter, pointer[letter]);
            }
        }
    }

    helper("", traversedTrie);
    return result;
}

console.log("Current wordlist: ");
console.log(words);
console.log();
console.log("Generated Trie:");
console.log(JSON.stringify(trie));
console.log();
console.log("Autocomplete letters:");
console.log('- suggestLettersFromPrefix(trie, "a")')
console.log(suggestLettersFromPrefix(trie, "a"));
console.log();
console.log('- suggestLettersFromPrefix(trie, "an")')
console.log(suggestLettersFromPrefix(trie, "an"));
console.log();
console.log('- suggestLettersFromPrefix(trie, "b")')
console.log(suggestLettersFromPrefix(trie, "b"));
console.log();
console.log("Autocomplete Words:");
console.log('- suggestWordsFromPrefix(trie, "a")')
console.log(suggestWordsFromPrefix(trie, "a"));
console.log()
console.log('- suggestWordsFromPrefix(trie, "an")')
console.log(suggestWordsFromPrefix(trie, "an"));

usage.txt

$ node trie.js
Current wordlist:
[ 'adjective', 'animal', 'animation', 'bridge', 'build' ]

Generated Trie:
{"a":{"d":{"j":{"e":{"c":{"t":{"i":{"v":{"e":{"_":0}}}}}}}},"n":{"i":{"m":{"a":{"l":{"_":0},"t":{"i":{"o":{"n":{"_":0}}}}}}}}},"b":{"r":{"i":{"d":{"g":{"e":{"_":0}}}}},"u":{"i":{"l":{"d":{"_":0}}}}}}

Autocomplete letters:
- suggestLettersFromPrefix(trie, "a")
[ 'd', 'n' ]

- suggestLettersFromPrefix(trie, "an")
[ 'i' ]

- suggestLettersFromPrefix(trie, "b")
[ 'r', 'u' ]

Autocomplete Words:
- suggestWordsFromPrefix(trie, "a")
[ 'adjective', 'animal', 'animation' ]

- suggestWordsFromPrefix(trie, "an")
[ 'animal', 'animation' ]