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

}