Created
September 3, 2017 11:02
-
-
Save alex3165/7edf50d3b86fdd06599e1bfcec7aeb64 to your computer and use it in GitHub Desktop.
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
function Node(data) { | |
this.data = data; | |
this.children = []; | |
} | |
class Tree { | |
constructor(rootData) { | |
this.root = new Node(rootData); | |
} | |
add(data, toNodeData) { | |
const parent = this.find(toNodeData); | |
parent.children.push(new Node(data)); | |
return this.root; | |
} | |
find(nodeData) { | |
const queue = [this.root]; | |
while(queue.length) { | |
const node = queue.shift(); | |
if (node.data === nodeData) { | |
return node; | |
} | |
for(let i = 0; i < node.children.length; i++) { | |
queue.push(node.children[i]); | |
} | |
} | |
return null; | |
} | |
getReportStack(name) { | |
let finalStack; | |
const recurse = (node, stackChild) => { | |
stackChild.push(node.data); | |
if (node.data === name) { | |
finalStack = stackChild; | |
} | |
for (let i = 0; i < node.children.length; i++) { | |
recurse(node.children[i], [...stackChild]); | |
} | |
} | |
recurse(this.root, []); | |
return finalStack; | |
} | |
} | |
const input = [ | |
'Sarah', | |
'Fred', | |
'June Tom', | |
'Tom Nathan', | |
'Tom Sarah', | |
'Nathan Qing', | |
'Nathan Fred' | |
] | |
const main = (input) => { | |
const firstSelected = input.shift(); | |
const secondSelected = input.shift(); | |
const root = input[0].split(' ')[0]; | |
const tree = new Tree(root); | |
input.forEach(vertexStr => { | |
const vertex = vertexStr.split(' '); | |
tree.add(vertex[1], vertex[0]); | |
}); | |
const first = tree.getReportStack(firstSelected); | |
const second = tree.getReportStack(secondSelected); | |
if (first.length < second.length) { | |
console.log(first[first.length - 2]); | |
} else { | |
console.log(second[second.length - 2]); | |
} | |
} | |
main(input); |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment