class BSTNode {
        constructor(data, left = null, right = null) {
            this.data = data;
            this.left = left;
            this.right = right;
        }

        insertNode(node) {
            let newNode = null;
            if (node.data <= this.data) {
                if (this.left) {
                    return this.left.insertNode(node);
                }

                newNode = new BSTNode(node.data);
                this.left = newNode;

                return newNode;

            } else if (node.data > this.data) {
                if (this.right) {
                    return this.right.insertNode(node);
                }

                newNode = new BSTNode(node.data);
                this.right = newNode;

                return newNode;
            }

            return this;
        }

        findNode(data) {
            if (this.data === data) {
                return this;
            } else if (data < this.data && this.left) {
                return this.left.findNode(data);
            } else if (data > this.data && this.right) {
                return this.right.findNode(data);
            }

            return null;
        }

        findMinNode() {
            if (!this.left) {
                return this;
            }

            return this.left.findMinNode();
        }
    }

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

        insert(data) {
            const newNode = new BSTNode(data);

            if (!this.root) {
                this.root = newNode;
                return this;
            }

            return this.root.insertNode(newNode);
        }

        delete(target, root = this.root) {
            if (!root) {
                return root;
            } else if (target < root.data) {
                root.left = this.delete(target, root.left);
            } else if (target > root.data) {
                root.right = this.delete(target, root.right);
            } else {
                // No child
                if (!root.left && !root.right) {
                    root = null;
                }

                // One child
                else if (root.left == null) {
                    root = root.right;
                } else if (root.right == null) {
                    root = root.left;
                }

                // Two children
                else {
                    const minNode = this.findMin(root.right);
                    root.data = minNode.data;
                    root.right = this.delete(minNode.data, root.right);
                }
            }

            return root;
        }

        find(data) {
            if (!this.root) {
                return null;
            }

            return this.root.findNode(data);
        }

        findMin(root = this.root) {
            if (!root) {
                return null;
            }

            return root.findMinNode();
        }

        /**
         * Find the in-order successor of a node
         *
         * @param data The data of the node to find its successor
         * @returns {null|BSTNode}
         */
        findSuccessor(data) {
            let current = this.find(data);

            if(!current) {
                return null;
            }

            if(current.right) {
                let rightNode = current.right;
                return this.findMin(rightNode);
            }

            else if(!current.right) {
                let ancestor = this.root;
                let successor = null;

                while(ancestor !== current) {
                    if(current.data < ancestor.data) {
                        successor = ancestor;
                        ancestor = ancestor.left;
                    }
                    else {
                        ancestor = ancestor.right;
                    }
                }

                return successor;
            }



            return null;
        }

        height(root) {
            if (!root) {
                return -1;
            }

            return Math.max(this.height(root.left), this.height(root.right)) + 1;
        }
  }