# Binary Search Tree (BST)

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; } }