I know this has been asked a million times, and there are a million instances of this online, but this is my blog…so this is my version.

This was a question asked on an Amazon coding interview:

Given a BST created from an array of number, calculate the distance between 2 nodes of the tree.

So if the input array was [5, 6, 3, 4, 2, 1], the tree would look like this:

So to calculate the distance between 1 and 4, we would do the following:

- Find the lowest common ancestor (LCA) for 1 and 4
- Count the number of hops from the LCA to 1
- Count the number of hops from the LCA to 4
- Combine them

…and that’s the distance: so in the case of 1 and 4, the distance is 3.

I’m not someone who writes things like this on a regular basis, preferring to utilize tried and tested libraries, but it was a good coding exercise for sure, and lot’s of fun.

So here is my implementation in ES6-style JavaScript

class BinarySearchTree {
constructor(list) {
this.tree = {};
this.branches = [];
for (let n in list) {
this.branches.push(this.branch(list[n]));
}
for (let [key, branch] of Object.entries(this.branches)) {
if (Object.entries(this.tree).length == 0) {
this.tree.root = {};
this.tree.root = Object.assign(branch, this.tree.root);
} else {
this.build(branch, this.tree.root);
}
}
return this;
}
branch(val) {
let branch = {
val: val,
lft: {},
rgt: {}
};
return branch;
}
build(branch, node) {
if (node.val > branch.val) {
if (Object.entries(node.lft).length == 0) {
node.lft = Object.assign(branch, node.lft);
} else {
this.build(branch, node.lft);
}
} else {
if (Object.entries(node.rgt).length == 0) {
node.rgt = Object.assign(branch, node.rgt);
} else {
this.build(branch, node.rgt);
}
}
}
getDistance(from, to) {
if (!this.find(this.tree.root, from) || !this.find(this.tree.root, to)) {
return -1;
}
let lca = this.findLowestCommonAncestor(from, to);
if (!lca) {
return -1;
}
let node = this.find(this.tree.root, lca);
let count = 0;
let counter = function(_node, _count, _direction, _specifier) {
while (_node.val != _specifier) {
_count ++;
_node = _node[_direction];
}
return _count;
};
count = counter(node, count, 'lft', from);
count = counter(node, count, 'rgt', to);
return count;
}
find (node, val) {
if (node.val == val) {
return node;
} else if (node.val > val) {
return this.find(node.lft, val);
} else if (node.val < val) {
return this.find(node.rgt, val);
}
return false;
}
findLowestCommonAncestor(node1Val, node2Val) {
let common = false;
let node1Ancestors = this.findAllAncestors(node1Val);
let node2Ancestors = this.findAllAncestors(node2Val);
if (node1Ancestors.length == 0 || node2Ancestors.length == 0) {
return false;
}
node1Ancestors = node1Ancestors.sort();
node2Ancestors = node2Ancestors.sort();
for (let n in node1Ancestors) {
if (node2Ancestors.indexOf(node1Ancestors[n]) != -1) {
common = node1Ancestors[n];
break;
}
}
return common;
}
findAllAncestors(nodeVal) {
let ancestors = [];
let iter = this.tree.root;
ancestors.push(iter.val);
while (iter.val != nodeVal) {
if (iter.val > nodeVal) {
iter = iter.lft;
} else if (iter.val <= nodeVal) {
iter = iter.rgt;
} else {
break;
}
if (iter != undefined) {
ancestors.push(iter.val);
}
}
return ancestors;
}
}