Skip to content

Instantly share code, notes, and snippets.

@manduks
Last active July 1, 2023 12:05
Show Gist options
  • Save manduks/7b539207de9d3ee4a51d66c2bfc72603 to your computer and use it in GitHub Desktop.
Save manduks/7b539207de9d3ee4a51d66c2bfc72603 to your computer and use it in GitHub Desktop.
Lowest Common Ancestor in a Binary Tree in Javascript
/*
Taking this tree as an example the output for
lowestCommonAncestor('k', 'j') => e
a
/ \
b c
/ \
d e
/ \
f g
/ \ \
h i j
/
k
*/
const tree = {
a: {
parent: null,
},
b: {
parent: 'a',
},
c: {
parent: 'a',
},
d: {
parent: 'b',
},
e: {
parent: 'b',
},
f: {
parent: 'e',
},
g: {
parent: 'e',
},
h: {
parent: 'f',
},
i: {
parent: 'f',
},
j: {
parent: 'g',
},
k: {
parent: 'i',
},
};
function getDepth(node) {
if (tree[node].parent) {
return getDepth(tree[node].parent) + 1;
}
return 0;
}
function walkN(node, n) {
if (n === 0) {
return node;
}
return walkN(tree[node].parent, n - 1);
}
function lowestCommonAncestor(a, b) {
const depthA = getDepth(a);
const depthB = getDepth(b);
let result;
let startNodeA = a;
let startNodeB = b;
if (depthA > depthB) {
startNodeA = walkN(a, depthA - depthB);
}
if (depthB > depthA) {
startNodeB = walkN(b, depthB - depthA);
}
while (!result) {
if (tree[startNodeA].parent) {
startNodeA = tree[startNodeA].parent;
}
if (tree[startNodeB].parent) {
startNodeB = tree[startNodeB].parent;
}
if (startNodeA === startNodeB) {
result = startNodeB;
}
}
console.log(result);
}
lowestCommonAncestor('k', 'j');
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment