Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Building a trie using Javascript. Credit to @dariothornhill
const routes = [['foo', 'bar'], ['foo'], ['products']]
function TrieNode(value) {
this.value = value;
this.children = []
}
const checkValue = (node, value) => {
return node.value === value;
}
function buildTrie() {
const leafMarker = false
const root = new TrieNode(null);
for (let x = 0; x < routes.length; x++) {
let current = root
const path = routes[x]
for (let y = 0; y < path.length; y++) {
console.log(path[y])
childIndex = current.children.findIndex(node => checkValue(node, path[y]))
console.log({ childIndex })
if (childIndex === -1) {
const newNode = new TrieNode(path[y])
current.children.push(newNode)
current = newNode
} else {
current = current.children[childIndex]
}
current.children.push(false)
}
}
return root;
}
const trieRoot = buildTrie(routes);
function searchTrie(root, pathList) {
console.log("searching...");
let current = root
let found = false
while (pathList.length > 0) {
childIndex = current.children.findIndex(node => checkValue(node, pathList[0]))
if (childIndex !== -1) {
pathList.shift()
current = current.children[childIndex]
} else {
return false;
}
console.log(pathList.length)
}
const result = current.children.findIndex(node => node === false)
console.log({ current, result })
return result !== -1 ? true : false;
}
console.log('search result:', searchTrie(trieRoot, ['foo']));
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment