Instantly share code, notes, and snippets.

@GreggSetzer /tree.js
Last active Jul 27, 2018

Embed
What would you like to do?
JavaScript Interview Question: Tree
class Node {
constructor(data) {
this.data = data;
this.children = [];
}
add(data) {
this.children.push(new Node(data));
}
remove(data) {
this.children = this.children.filter(node => node.data !== data);
}
}
class Tree {
constructor() {
this.root = null;
}
//Example of traversing breadth first.
traverseBF(fn) {
let arr = [this.root];
while (arr.length) {
const node = arr.shift();
arr.push(...node.children);
fn(node);
}
}
//Example of traversing depth first.
traverseDF(fn) {
let arr = [this.root];
while (arr.length) {
const node = arr.shift();
arr.unshift(...node.childen);
fn(node);
}
}
}
function levelWidth(root) {
const counters = [0];
const arr = [root, null];
while (arr.length > 1) {
const node = arr.shift();
if (node) {
arr.push(...node.children);
counters[counters.length - 1]++;
} else {
counters.push(0);
arr.push(null);
}
}
return counters;
}
(() => {
const letters = [];
const t = new Tree();
t.root = new Node('a');
t.root.add('b');
t.root.add('c');
t.root.children[0].add('d');
t.traverseBF(node => {
letters.push(node.data);
});
expect(letters).toEqual(['a', 'b', 'c', 'd']);
})();
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment