Created
September 11, 2019 16:00
-
-
Save vinnymac/7a9691eb3601274adec03d1b43ac1e0b to your computer and use it in GitHub Desktop.
Tree Traversal DFS vs BFS JavaScript
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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)) |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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)) |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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