TREE = {
// create a tree map of the input
const map = new Map();
input.forEach((orbit) => {
const [parent, child] = orbit.split(')');
if (!map.has(parent)) {
map.set(parent, { children: [child] });
} else {
const children = map.get(parent).children;
children.push(child);
map.set(parent, Object.assign(map.get(parent), { children }));
}
if (!map.has(child)) {
map.set(child, { children: [], parent });
} else {
map.set(child, Object.assign(map.get(child), { parent }));
}
});
return map;
}
{
const map = TREE;
const dfs = (node, depth) => {
return depth + map.get(node).children.reduce((acc, val) => acc + dfs(val, depth + 1), 0);
}
// COM is the root of the tree
return dfs('COM', 0);
}
{
// find first common ancestor between YOU & SAN
const map = TREE;
const yourAncestors = [];
let node = map.get('YOU');
while (node) {
yourAncestors.push(node.parent);
node = map.get(node.parent);
}
node = map.get('SAN');
let dist = 0;
while (node && !yourAncestors.includes(node.parent)) {
dist++;
node = map.get(node.parent);
}
const commonAncestor = node.parent;
return dist + yourAncestors.indexOf(commonAncestor);
}
Purpose-built for displays of data
Observable is your go-to platform for exploring data and creating expressive data visualizations. Use reactive JavaScript notebooks for prototyping and a collaborative canvas for visual data exploration and dashboard creation.
