Delete a Leaf Node in a Binary Search Tree last test fails

Delete a Leaf Node in a Binary Search Tree last test fails
0

Delete a Leaf Node in a Binary Search Tree

Hi,
My remove() method fails at the last test and I can’t find the issue.

my code
var displayTree = tree => console.log(JSON.stringify(tree, null, 2));
function Node(value) {
    this.value = value;
    this.left = null;
    this.right = null;
}
function BinarySearchTree() {
    this.root = null;
    this.add = function(value) {
        const newNode = new Node(value);
        
        this.root === null 
            ? this.root = newNode
            : this.insertNode(this.root, newNode)
        ;
        
    };
    
    this.insertNode = function(node, newNode) {
        
        if (newNode.value < node.value) {
            node.left === null
                ? node.left = newNode
                : this.insertNode(node.left, newNode)
            ;
        } else {
            node.right === null 
                ? node.right = newNode
                : this.insertNode(node.right, newNode)
            ;
        }
    };
    
    this.findMin = function() {
        if (!(this.root)) return null;
        let node = this.root;
        while (node.left) {
            node = node.left;
        }
        return node.value;
    };

    this.findMax = function() {
        if (!(this.root)) return null;
        let node = this.root;
        while (node.right) {
            node = node.right;
        }
        return node.value;
    };
    
    this.isPresent = function(value) {
        
        const findValue = function(node, value) {
            if (!(node)) {
                result = false;
                return;
            }
            if (node.value === value) {
                result = true;
                return;
            }
            if (node.value < value) {
                findValue(node.right, value);
            } else {
                findValue(node.left, value);
            }
        };
        
        let result = false;
        if (value === undefined || 
            this.root === null || 
            !(Number.isInteger(value)) ) {
            return false;
        }
        findValue(this.root, value);
        return result;
    };
    
    let distance, minDistance, maxDistance;
    const countStep = node => {
//        console.log(node.value, "on level", distance);
        if (!(node.left) && !(node.right)){
            // this is a leaf node
//            console.log("leaf node", node.value, "on level", distance);
            if (minDistance > distance) minDistance = distance;
            if (maxDistance < distance) maxDistance = distance;
            distance --;
            return;
        }
        
        if (node.left) {
            distance ++
            countStep(node.left);
        }
        if (node.right) {
            distance ++;
            countStep(node.right);
        }
    };
    
    this.findMinHeight = function() {
        if (!(this.root)) return -1;
        distance = 1;
        minDistance = Infinity;
        countStep(this.root.left);
        distance = 1;
        countStep(this.root.right);
        return  minDistance;
    };
    
    this.findMaxHeight = function() {
        if (!(this.root)) return -1;
        distance = 1;
        maxDistance = -Infinity;
        countStep(this.root.left);
        distance = 1;
        countStep(this.root.right);
        return  maxDistance;
    };
    
    this.isBalanced = function() {
        return (this.findMaxHeight() - this.findMinHeight()) < 2;
    };
    
    this.inorder = function(node = this.root, orderedList = []) {
        if (node) {
            this.inorder(node.left, orderedList);
            orderedList.push(node.value);
            this.inorder(node.right, orderedList);
        }
        return orderedList.length 
            ? orderedList 
            : null;
    };
    
    this.preorder = function(node = this.root, orderedList = []) {
        if (node) {
            orderedList.push(node.value);
            this.preorder(node.left, orderedList);
            this.preorder(node.right, orderedList);
        }
        return orderedList.length 
            ? orderedList 
            : null;
    };
    
    this.postorder = function(node = this.root, orderedList = []) {
        if (node) {
            this.postorder(node.left, orderedList);
            this.postorder(node.right, orderedList);
            orderedList.push(node.value);
        }
        return orderedList.length 
            ? orderedList 
            : null;
    };
    
    this.orderOnLevel = function(queueList = [this.root], levelOrderList = [], left = "left", right = "right") {
        while (queueList.length > 0 && queueList[0] !== null) {
            const node = queueList.shift();
            levelOrderList.push(node.value);
            if (node[left]) queueList.push(node[left]);
            if (node[right]) queueList.push(node[right]);
            this.orderOnLevel(queueList, levelOrderList, left, right);
        }
        return levelOrderList.length 
            ? levelOrderList
            : null;
    };
    
    this.levelOrder = function() {
        return this.orderOnLevel();
    };
    
    this.reverseLevelOrder = function() {
        return this.orderOnLevel([this.root], [], "right", "left");
    };
    
    // this function return the parent and child node with the given value or null if the value not found:
    this.findValue = function(value) {
        let node = this.root;
        let parentNode = node;
        while (node) {
            if (node.value === value) return {parent : parentNode, child: node};
            parentNode = node;
            if (node.value < value) {
                node = node.right;
            } else {
                node = node.left
            }
        }
        return null;
    };
    
    this.remove = function(value) {
        const rootNode = this.root;
        // if the value miss or incorrect or have not rootNode:
        if (value === undefined || 
            typeof value !== "number" ||
            !(Number.isInteger(value)) ||
            !(rootNode)) {
            return null;
        } 
            
        // if we have only one node:
        if (rootNode.left === null && 
            rootNode.right === null) {
            return rootNode.value === value 
                ? this.root = null 
                : null;
        } 
        const parentAndChild = this.findValue(value);
        if (!(parentAndChild)) return null; // value not found
        const parentNode = parentAndChild.parent;
        const childNode = parentAndChild.child;
        if (childNode.left === null && 
            childNode.right === null) {
            // leaf node:
            if (parentNode.left.value === value) {
                parentNode.left = null;
            } else {
                parentNode.right = null;
            }
        }
    };
}

const isBinarySearchTree = tree => {
    if (!(tree.root) || 
        !(tree.root.hasOwnProperty("left")) || 
        !(tree.root.hasOwnProperty("right"))) {
        return false;
    }
    
    let result = true;
    
    const checkValue = (parentNode) => {
        if (parentNode.left) {
            const leftNode = parentNode.left;
            if (leftNode.value >= parentNode.value) {
                result = false;
                return;
            } else {
                checkValue(leftNode);
            }
        }
        
        if (parentNode.right) {
            const rightNode = parentNode.right;
            if (rightNode.value <= parentNode.value) {
                result = false;
                return;
            } else {
                checkValue(rightNode);
            }
        }
    };
    
    checkValue(tree.root);
    return result;
};

const myTree = new BinarySearchTree();
myTree.add(8);
myTree.add(3);
myTree.add(10);
myTree.add(1);
myTree.add(6);
myTree.add(14);
myTree.add(4);
myTree.add(7);
myTree.add(13);
//myTree.add(12);
//console.log(myTree.findMin());
//console.log(myTree.findMax());
//console.log(myTree.isPresent(10));
//console.log(myTree.root);
//console.log(isBinarySearchTree(myTree));
//console.log("the minimum level is:", myTree.findMinHeight());
//console.log("the maximum level is:", myTree.findMaxHeight());
//console.log(myTree.isBalanced());
//console.log(myTree.inorder());
//console.log(myTree.preorder());
//console.log(myTree.postorder());
//console.log(myTree.levelOrder());
//console.log(myTree.reverseLevelOrder());
//console.log(myTree.remove(1));
console.log(myTree.remove(4));
//console.log(myTree.remove(7));
//console.log(myTree.remove(13));
displayTree(myTree);

I went to the next lesson to remove node with one child only:
the fails is still appear and I don’t know why.
The node with one child deleted…

Delete a Node with One Child in a Binary Search Tree

my code
var displayTree = tree => console.log(JSON.stringify(tree, null, 2));
function Node(value) {
    this.value = value;
    this.left = null;
    this.right = null;
}
function BinarySearchTree() {
    this.root = null;
    this.add = function(value) {
        const newNode = new Node(value);
        
        this.root === null 
            ? this.root = newNode
            : this.insertNode(this.root, newNode)
        ;
        
    };
    
    this.insertNode = function(node, newNode) {
        
        if (newNode.value < node.value) {
            node.left === null
                ? node.left = newNode
                : this.insertNode(node.left, newNode)
            ;
        } else {
            node.right === null 
                ? node.right = newNode
                : this.insertNode(node.right, newNode)
            ;
        }
    };
    
    this.findMin = function() {
        if (!(this.root)) return null;
        let node = this.root;
        while (node.left) {
            node = node.left;
        }
        return node.value;
    };

    this.findMax = function() {
        if (!(this.root)) return null;
        let node = this.root;
        while (node.right) {
            node = node.right;
        }
        return node.value;
    };
    
    this.isPresent = function(value) {
        
        const findValue = function(node, value) {
            if (!(node)) {
                result = false;
                return;
            }
            if (node.value === value) {
                result = true;
                return;
            }
            if (node.value < value) {
                findValue(node.right, value);
            } else {
                findValue(node.left, value);
            }
        };
        
        let result = false;
        if (value === undefined || 
            this.root === null || 
            !(Number.isInteger(value)) ) {
            return false;
        }
        findValue(this.root, value);
        return result;
    };
    
    let distance, minDistance, maxDistance;
    const countStep = node => {
//        console.log(node.value, "on level", distance);
        if (!(node.left) && !(node.right)){
            // this is a leaf node
//            console.log("leaf node", node.value, "on level", distance);
            if (minDistance > distance) minDistance = distance;
            if (maxDistance < distance) maxDistance = distance;
            distance --;
            return;
        }
        
        if (node.left) {
            distance ++
            countStep(node.left);
        }
        if (node.right) {
            distance ++;
            countStep(node.right);
        }
    };
    
    this.findMinHeight = function() {
        if (!(this.root)) return -1;
        distance = 1;
        minDistance = Infinity;
        countStep(this.root.left);
        distance = 1;
        countStep(this.root.right);
        return  minDistance;
    };
    
    this.findMaxHeight = function() {
        if (!(this.root)) return -1;
        distance = 1;
        maxDistance = -Infinity;
        countStep(this.root.left);
        distance = 1;
        countStep(this.root.right);
        return  maxDistance;
    };
    
    this.isBalanced = function() {
        return (this.findMaxHeight() - this.findMinHeight()) < 2;
    };
    
    this.inorder = function(node = this.root, orderedList = []) {
        if (node) {
            this.inorder(node.left, orderedList);
            orderedList.push(node.value);
            this.inorder(node.right, orderedList);
        }
        return orderedList.length 
            ? orderedList 
            : null;
    };
    
    this.preorder = function(node = this.root, orderedList = []) {
        if (node) {
            orderedList.push(node.value);
            this.preorder(node.left, orderedList);
            this.preorder(node.right, orderedList);
        }
        return orderedList.length 
            ? orderedList 
            : null;
    };
    
    this.postorder = function(node = this.root, orderedList = []) {
        if (node) {
            this.postorder(node.left, orderedList);
            this.postorder(node.right, orderedList);
            orderedList.push(node.value);
        }
        return orderedList.length 
            ? orderedList 
            : null;
    };
    
    this.orderOnLevel = function(queueList = [this.root], levelOrderList = [], left = "left", right = "right") {
        while (queueList.length > 0 && queueList[0] !== null) {
            const node = queueList.shift();
            levelOrderList.push(node.value);
            if (node[left]) queueList.push(node[left]);
            if (node[right]) queueList.push(node[right]);
            this.orderOnLevel(queueList, levelOrderList, left, right);
        }
        return levelOrderList.length 
            ? levelOrderList
            : null;
    };
    
    this.levelOrder = function() {
        return this.orderOnLevel();
    };
    
    this.reverseLevelOrder = function() {
        return this.orderOnLevel([this.root], [], "right", "left");
    };
    
    // this function return the parent and child node with the given value or null if the value not found:
    this.findValue = function(value) {
        let node = this.root;
        let parentNode = node;
        while (node) {
            if (node.value === value) return {parent : parentNode, child: node};
            parentNode = node;
            if (node.value < value) {
                node = node.right;
            } else {
                node = node.left;
            }
        }
        return null;
    };
    
    this.remove = function(value) {
        const rootNode = this.root;
        // if the value miss or incorrect or have not rootNode:
        if (value === undefined || 
            typeof value !== "number" ||
            !(Number.isInteger(value)) ||
            !(rootNode)) {
            return null;
        } 
            
        // if we have only one node:
        if (rootNode.left === null && 
            rootNode.right === null) {
            return rootNode.value === value 
                ? this.root = null 
                : null;
        } 
        const parentAndChild = this.findValue(value);
        if (!(parentAndChild)) return null; // value not found
        const parentNode = parentAndChild.parent;
        const childNode = parentAndChild.child;
        // leaf node:
        if (childNode.left === null && 
            childNode.right === null) {
            if (parentNode.left.value === value) {
                parentNode.left = null;
            } else {
                parentNode.right = null;
            }
            return;
        }
        if (parentNode.left && parentNode.left.value === value) {
            // only one child node on left side:
            if (childNode.left && !(childNode.right)) {
                parentNode.left = childNode.left;
            } else if (childNode.right && !(childNode.left)) {
                parentNode.left = childNode.right;
            }
        }
        if (parentNode.right && parentNode.right.value === value) {
            // only one child node on right side:
            if (childNode.left && !(childNode.right)) {
                parentNode.right = childNode.left;
            } else if (childNode.right && !(childNode.left)) {
                parentNode.right = childNode.right;
            }
        }
    };
}

const isBinarySearchTree = tree => {
    if (!(tree.root) || 
        !(tree.root.hasOwnProperty("left")) || 
        !(tree.root.hasOwnProperty("right"))) {
        return false;
    }
    
    let result = true;
    
    const checkValue = (parentNode) => {
        if (parentNode.left) {
            const leftNode = parentNode.left;
            if (leftNode.value >= parentNode.value) {
                result = false;
                return;
            } else {
                checkValue(leftNode);
            }
        }
        
        if (parentNode.right) {
            const rightNode = parentNode.right;
            if (rightNode.value <= parentNode.value) {
                result = false;
                return;
            } else {
                checkValue(rightNode);
            }
        }
    };
    
    checkValue(tree.root);
    return result;
};

const myTree = new BinarySearchTree();
myTree.add(8);
myTree.add(3);
myTree.add(10);
myTree.add(1);
myTree.add(6);
myTree.add(14);
myTree.add(4);
myTree.add(7);
myTree.add(13);
myTree.add(5);
//myTree.add(12);
//console.log(myTree.findMin());
//console.log(myTree.findMax());
//console.log(myTree.isPresent(10));
//console.log(myTree.root);
//console.log(isBinarySearchTree(myTree));
//console.log("the minimum level is:", myTree.findMinHeight());
//console.log("the maximum level is:", myTree.findMaxHeight());
//console.log(myTree.isBalanced());
//console.log(myTree.inorder());
//console.log(myTree.preorder());
//console.log(myTree.postorder());
//console.log(myTree.levelOrder());
//console.log(myTree.reverseLevelOrder());
//console.log(myTree.remove(1));
displayTree(myTree);
console.log(myTree.remove(4));
displayTree(myTree);
//console.log(myTree.remove(7));
//console.log(myTree.remove(13));

Delete a Node with Two Children

I completed the remove() method to delete with two children. This is Fails on test too while as I see delete well the node…
Is anyone can take a look to

my code
var displayTree = tree => console.log(JSON.stringify(tree, null, 2));
function Node(value) {
    this.value = value;
    this.left = null;
    this.right = null;
}
function BinarySearchTree() {
    this.root = null;
    this.add = function(value) {
        const newNode = new Node(value);
        
        this.root === null 
            ? this.root = newNode
            : this.insertNode(this.root, newNode)
        ;
        
    };
    
    this.insertNode = function(node, newNode) {
        
        if (newNode.value < node.value) {
            node.left === null
                ? node.left = newNode
                : this.insertNode(node.left, newNode)
            ;
        } else {
            node.right === null 
                ? node.right = newNode
                : this.insertNode(node.right, newNode)
            ;
        }
    };
    
    this.findMin = function(targetNode = this.root) {
        if (!(targetNode)) return null;
        let node = targetNode;
        while (node.left) {
            node = node.left;
        }
        return node.value;
    };

    this.findMax = function() {
        if (!(this.root)) return null;
        let node = this.root;
        while (node.right) {
            node = node.right;
        }
        return node.value;
    };
    
    this.isPresent = function(value) {
        
        const findValue = function(node, value) {
            if (!(node)) {
                result = false;
                return;
            }
            if (node.value === value) {
                result = true;
                return;
            }
            if (node.value < value) {
                findValue(node.right, value);
            } else {
                findValue(node.left, value);
            }
        };
        
        let result = false;
        if (value === undefined || 
            this.root === null || 
            !(Number.isInteger(value)) ) {
            return false;
        }
        findValue(this.root, value);
        return result;
    };
    
    let distance, minDistance, maxDistance;
    const countStep = node => {
//        console.log(node.value, "on level", distance);
        if (!(node.left) && !(node.right)){
            // this is a leaf node
//            console.log("leaf node", node.value, "on level", distance);
            if (minDistance > distance) minDistance = distance;
            if (maxDistance < distance) maxDistance = distance;
            distance --;
            return;
        }
        
        if (node.left) {
            distance ++
            countStep(node.left);
        }
        if (node.right) {
            distance ++;
            countStep(node.right);
        }
    };
    
    this.findMinHeight = function() {
        if (!(this.root)) return -1;
        distance = 1;
        minDistance = Infinity;
        countStep(this.root.left);
        distance = 1;
        countStep(this.root.right);
        return  minDistance;
    };
    
    this.findMaxHeight = function() {
        if (!(this.root)) return -1;
        distance = 1;
        maxDistance = -Infinity;
        countStep(this.root.left);
        distance = 1;
        countStep(this.root.right);
        return  maxDistance;
    };
    
    this.isBalanced = function() {
        return (this.findMaxHeight() - this.findMinHeight()) < 2;
    };
    
    this.inorder = function(node = this.root, orderedList = []) {
        if (node) {
            this.inorder(node.left, orderedList);
            orderedList.push(node.value);
            this.inorder(node.right, orderedList);
        }
        return orderedList.length 
            ? orderedList 
            : null;
    };
    
    this.preorder = function(node = this.root, orderedList = []) {
        if (node) {
            orderedList.push(node.value);
            this.preorder(node.left, orderedList);
            this.preorder(node.right, orderedList);
        }
        return orderedList.length 
            ? orderedList 
            : null;
    };
    
    this.postorder = function(node = this.root, orderedList = []) {
        if (node) {
            this.postorder(node.left, orderedList);
            this.postorder(node.right, orderedList);
            orderedList.push(node.value);
        }
        return orderedList.length 
            ? orderedList 
            : null;
    };
    
    this.orderOnLevel = function(queueList = [this.root], levelOrderList = [], left = "left", right = "right") {
        while (queueList.length > 0 && queueList[0] !== null) {
            const node = queueList.shift();
            levelOrderList.push(node.value);
            if (node[left]) queueList.push(node[left]);
            if (node[right]) queueList.push(node[right]);
            this.orderOnLevel(queueList, levelOrderList, left, right);
        }
        return levelOrderList.length 
            ? levelOrderList
            : null;
    };
    
    this.levelOrder = function() {
        return this.orderOnLevel();
    };
    
    this.reverseLevelOrder = function() {
        return this.orderOnLevel([this.root], [], "right", "left");
    };
    
    // this function return the parent and child node with the given value or null if the value not found:
    this.findValue = function(value) {
        let node = this.root;
        let parentNode = node;
        while (node) {
            if (node.value === value) return {parent : parentNode, child: node};
            parentNode = node;
            if (node.value < value) {
                node = node.right;
            } else {
                node = node.left;
            }
        }
        return null;
    };
    
    this.remove = function(value) {
        const rootNode = this.root;
        // if the value miss or incorrect or have not rootNode:
        if (value === undefined || 
            typeof value !== "number" ||
            !(Number.isInteger(value)) ||
            !(rootNode)) {
            return null;
        } 
            
        // if we have only one node:
        if (rootNode.left === null && 
            rootNode.right === null) {
            return rootNode.value === value 
                ? this.root = null 
                : null;
        } 
        const parentAndChild = this.findValue(value);
        if (!(parentAndChild)) return null; // value not found
        const parentNode = parentAndChild.parent;
        const childNode = parentAndChild.child;
        // leaf node:
        if (childNode.left === null && 
            childNode.right === null) {
            if (parentNode.left.value === value) {
                parentNode.left = null;
            } else {
                parentNode.right = null;
            }
            return;
        }
        
        // one child:
        if (parentNode.left && parentNode.left.value === value) {
            // only one child node on left side:
            if (childNode.left && !(childNode.right)) {
                parentNode.left = childNode.left;
            } else if (childNode.right && !(childNode.left)) {
                parentNode.left = childNode.right;
            }
        }
        if (parentNode.right && parentNode.right.value === value) {
            // only one child node on right side:
            if (childNode.left && !(childNode.right)) {
                parentNode.right = childNode.left;
            } else if (childNode.right && !(childNode.left)) {
                parentNode.right = childNode.right;
            }
        }
        
        // two children:
        if (childNode.left && childNode.right) {
            const minValueOnRight = this.findMin(childNode.right);
            this.remove(minValueOnRight);
            childNode.value = minValueOnRight;
        }
    };
}

const isBinarySearchTree = tree => {
    if (!(tree.root) || 
        !(tree.root.hasOwnProperty("left")) || 
        !(tree.root.hasOwnProperty("right"))) {
        return false;
    }
    
    let result = true;
    
    const checkValue = (parentNode) => {
        if (parentNode.left) {
            const leftNode = parentNode.left;
            if (leftNode.value >= parentNode.value) {
                result = false;
                return;
            } else {
                checkValue(leftNode);
            }
        }
        
        if (parentNode.right) {
            const rightNode = parentNode.right;
            if (rightNode.value <= parentNode.value) {
                result = false;
                return;
            } else {
                checkValue(rightNode);
            }
        }
    };
    
    checkValue(tree.root);
    return result;
};

const myTree = new BinarySearchTree();
myTree.add(8);
myTree.add(3);
myTree.add(10);
myTree.add(1);
myTree.add(6);
myTree.add(14);
myTree.add(4);
myTree.add(7);
myTree.add(13);
myTree.add(5);
myTree.add(12);
//console.log(myTree.findMin());
//console.log(myTree.findMax());
//console.log(myTree.isPresent(10));
//console.log(myTree.root);
//console.log(isBinarySearchTree(myTree));
//console.log("the minimum level is:", myTree.findMinHeight());
//console.log("the maximum level is:", myTree.findMaxHeight());
//console.log(myTree.isBalanced());
//console.log(myTree.inorder());
//console.log(myTree.preorder());
//console.log(myTree.postorder());
//console.log(myTree.levelOrder());
//console.log(myTree.reverseLevelOrder());
//console.log(myTree.remove(1));
//displayTree(myTree);
console.log(myTree.remove(8));
console.log(myTree.root);

please?