binary-search-tree.js

class Node {
    constructor (value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

class BinarySearchTree {
    constructor () {
        this.root = null;
    }

    // O(log N)
    insert (value) {
        const node = new Node(value);

        if (!this.root) {
            this.root = node;
            return this;
        } else {
            let current = this.root;
            while (current) {
                if (current.value === value) {
                    return undefined;
                }

                if (current.value > value) {
                    if (!current.left) {
                        current.left = node;
                        return this;
                    }
                    current = current.left;
                } else {
                    if (!current.right) {
                        current.right = node;
                        return this;
                    }
                    current = current.right;
                }
            }
        }
    }

    // O(log N)
    find (value) {
        if (!this.root) {
            return undefined;
        }
        let current = this.root;
        while (current && current.value !== value) {
            if (current.value > value) {
                current = current.left;
            } else {
                current = current.right;
            }
        }
        return current;
    }

    breadthFirstSearch () {
        const queue = [];
        const result = [];

        if (!this.root) return result;

        queue.push(this.root);

        while (queue.length) {
            const node = queue.shift();
            result.push(node.value);
            if (node.left) queue.push(node.left);
            if (node.right) queue.push(node.right);
        }

        return result;
    }

    depthFirstSearchPreOrder () {
        const result = [];

        function traverse (node) {
            result.push(node.value);
            if (node.left) traverse(node.left);
            if (node.right) traverse(node.right);
        }

        traverse(this.root);

        return result;
    }

    depthFirstSearchPostOrder () {
        const result = [];

        function traverse (node) {
            if (node.left) traverse(node.left);
            if (node.right) traverse(node.right);
            result.push(node.value);
        }

        traverse(this.root);

        return result;
    }

    depthFirstSearchInOrder () {
        const result = [];

        function traverse (node) {
            if (node.left) traverse(node.left);
            result.push(node.value);
            if (node.right) traverse(node.right);
        }

        traverse(this.root);

        return result;
    }

    remove (value) {
        if (!this.root) {
            return undefined;
        }

        let parent = null;
        let current = this.root;

        while (current && current.value !== value) {
            parent = current;
            if (current.value > value) {
                current = current.left;
            } else {
                current = current.right;
            }
        }

        if (!current) {
            return undefined;
        }

        if (!current.left && !current.right) {
            if (parent.left && parent.left.value === value) {
                parent.left = null;
            } else if (parent.right && parent.right.value === value) {
                parent.right = null;
            }
        } else if (!current.left && current.right) {
            if (parent.left && parent.left.value === value) {
                parent.left = current.right;
            } else if (parent.right && parent.right.value === value) {
                parent.right = current.right;
            }
        } else if (current.left && !current.right) {
            if (parent.left && parent.left.value === value) {
                parent.left = current.left;
            } else if (parent.right && parent.right.value === value) {
                parent.right = current.left;
            }
        } else if (current.left && current.right) {
            const deleted = Object.assign({}, current);
            let successor = current.right;
            parent = current;
            while (successor.left) {
                parent = successor;
                successor = successor.left;
            }
            current.value = successor.value;
            if (parent.left && parent.left.value === successor.value) {
                parent.left = successor.right;
            } else if (parent.right && parent.right.value === successor.value) {
                parent.right = successor.right;
            }
            return deleted;
        }
        return current;
    }
}

const tree = new BinarySearchTree();
tree.insert(22);
tree.insert(49);
tree.insert(85);
tree.insert(66);
tree.insert(95);
tree.insert(90);
tree.insert(100);
tree.insert(88);
tree.insert(93);
tree.insert(89);
tree.remove(85);