Skip to content

Instantly share code, notes, and snippets.

@vinnymac
Created September 11, 2019 16:00
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save vinnymac/7a9691eb3601274adec03d1b43ac1e0b to your computer and use it in GitHub Desktop.
Save vinnymac/7a9691eb3601274adec03d1b43ac1e0b to your computer and use it in GitHub Desktop.
Tree Traversal DFS vs BFS JavaScript
class BFSTree extends Tree {
traverse(callback) {
const queue = [this.graph];
let node
while (queue.length > 0) {
node = queue.shift();
callback(node.value);
if (!node.children) continue;
node.children.forEach(child => queue.push(child));
}
}
}
// grow(new BFSTree('coconut')).traverse((v) => console.log(v))
class DFSTree extends Tree {
traverse(callback) {
const stack = [this.graph];
let node;
while (stack.length > 0) {
node = stack.pop();
callback(node.value);
if (!node.children) continue;
for (let i = node.children.length - 1; i >= 0; i--) {
stack.push(node.children[i]);
}
}
}
}
// grow(new DFSTree('pineapple')).traverse((v) => console.log(v))
class Tree {
constructor(value) {
this.graph = {
value,
children: [],
};
}
}
function grow(tree, maxDepth = 3, maxWidth = 3) {
new Array(maxWidth).fill('').forEach((x, i) => {
tree.graph.children.push({ value: tree.graph.value + i, children: [] })
})
tree.graph.children.forEach((c) => {
const randDepth = Math.floor(Math.random() * maxDepth + 1)
new Array(randDepth).fill('').forEach((x, i) => {
c.children.push({ value: `${tree.graph.value}${maxDepth}${i}`, children: [] })
})
})
return tree
}
// grow(new Tree('apple'))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment