Binary Search Tree

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

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

    insert(value) {
        if (this.root === null) {
            this.root = new BstNode(value);
            return this;
        }

        let current = this.root;
        while (true) {
            if (value === current.value) {
                return this;
            }

            if (value < current.value) {
                if (current.left === null) {
                    current.left = new BstNode(value);
                    return this;
                }
                current = current.left;
            } else {
                if (current.right === null) {
                    current.right = new BstNode(value);
                    return this;
                }
                current = current.right;
            }
        }
    }

    contains(value) {
        return this.find(value) !== null;
    }

    find(value) {
        let current = this.root;
        while (current) {
            if (value === current.value) {
                return current;
            }
            current = value < current.value ? current.left : current.right;
        }
        return null;
    }

    min(node = this.root) {
        if (!node) {
            return null;
        }
        while (node.left) {
            node = node.left;
        }
        return node.value;
    }

    max(node = this.root) {
        if (!node) {
            return null;
        }
        while (node.right) {
            node = node.right;
        }
        return node.value;
    }

    remove(value) {
        this.root = this._removeNode(this.root, value);
        return this;
    }

    inOrder() {
        const values = [];
        this._walk(this.root, values);
        return values;
    }

    _walk(node, values) {
        if (!node) {
            return;
        }
        this._walk(node.left, values);
        values.push(node.value);
        this._walk(node.right, values);
    }

    _minNode(node) {
        while (node.left) {
            node = node.left;
        }
        return node;
    }

    _removeNode(node, value) {
        if (!node) {
            return null;
        }

        if (value < node.value) {
            node.left = this._removeNode(node.left, value);
            return node;
        }

        if (value > node.value) {
            node.right = this._removeNode(node.right, value);
            return node;
        }

        if (!node.left) {
            return node.right;
        }
        if (!node.right) {
            return node.left;
        }

        const successor = this._minNode(node.right);
        node.value = successor.value;
        node.right = this._removeNode(node.right, successor.value);
        return node;
    }
}

const tree = new BinarySearchTree();
tree.insert(10).insert(5).insert(15).insert(5).insert(3);

console.log(tree.contains(7)); // false
console.log(tree.inOrder());   // [3, 5, 10, 15]
console.log(tree.min(), tree.max()); // 3 15

tree.remove(10);
console.log(tree.inOrder());   // [3, 5, 15]