binarySearchTree.js

// This is how tree should look like
// const tree = {
//     root: {
//         left: {
//             left: {
//                 left: null,
//                 right: null,
//                 value: 3
//             },
//             right: {
//                 left: null,
//                 right: null,
//                 value: 8
//             },
//             value:  5
//         },
//         right: {
//             left: {
//                 left: {
//                     left: null,
//                     right: null,
//                     value: 16
//                 },
//                 right: {
//                     left: null,
//                     right: null,
//                     value: 18
//                 },
//                 value: 17
//             },
//             right: {
//                 left: {
//                     left: {
//                         left: null,
//                         right: null,
//                         value: 21
//                     },
//                     right: {
//                         left: null,
//                         right: null,
//                         value: 23
//                     },
//                     value: 22
//                 },
//                 right: {
//                     left: null,
//                     right: null,
//                     value: 30
//                 },
//                 value: 24
//             },
//             value: 20
//         },
//         value: 10
//     },
//     metadata: {
//         string: 'schema of the tree does not required having metadata'
//     }
// }

function treeMaximumValueNode_Link(tree) {
    let tempPointer = tree.right || tree;   
    while (tempPointer.right !== null) {
        tempPointer = tempPointer.right;
    }
    return tempPointer;
}

function treeMinimumValueNode_Link(tree) {
    let tempPointer = tree.left || tree;
    while (tempPointer.left !== null) {
        tempPointer = tempPointer.left;
    }
    return tempPointer;
}

function treeWalk(tree, container) {
    if (tree.left == null) {
        if (tree.right !== null) {
            treeWalk(tree.right, container);
        }

        container.push(tree.value);
        return tree.value;
    }

    treeWalk(tree.left, container);

    if (tree.right === null) {
        container.push(tree.value);
        return tree.value;
    }
    
    container.push(tree.value);
    treeWalk(tree.right, container);
}

function treeInsertion(tree, value) {
    let rightNode = tree.right;
    let leftNode = tree.left;

    if (rightNode === null) {
        if (value > tree.value) {
            tree.right = {
                left: null,
                right: null,
                value: value
            }

            return true;
        }
    } 

    if (leftNode === null) {
        if (value < tree.value) {
            tree.left = {
                left: null,
                right: null,
                value: value
            }

            return true;
        }
    }

    if (value > rightNode.value) {
        const newRightNode = {
            left: rightNode,
            right: null,
            value: value
        }

        tree.right = newRightNode;
    } else if (leftNode.value < value && value < rightNode.value) {
        if (value < tree.value) {
            treeInsertion(tree.left, value);
        } else {
            treeInsertion(tree.right, value);
        }
    } else {
        treeInsertion(tree.left, value);
    }
}

function treeDeletion(tree, key) {
    // Find node to delete.
    if (tree !== null) {
        var current = tree;
        var stack = [];
        
        while (current) {
            stack.push(current);
            
            if (current.value === key) {
                // Found the node to delete.
                stack.pop();
                var parent = stack.pop();
    
                if (!current.left && !current.right) {
                    // No children, just remove the node.
                    if (parent && parent.left && parent.left.value === current.value) {
                        parent.left = null;
                    }
                    else if (parent) {
                        parent.right = null;
                    }
                    else {
                        // No parent, this must be the root node.
                        tree = [];
                    }
                }
                else if (current.left && !current.right) {
                    // One left child node.
                    if (parent && parent.left && parent.left.value === current.value) {
                        parent.left = current.left;
                    }
                    else if (parent) {
                        parent.right = current.left;
                    }
                    else {
                        // No parent, this must be the root node.
                        tree = current.left;
                    }
                }
                else if (current.right && !current.left) {
                    // One right child node.
                    if (parent && parent.left && parent.left.value === current.value) {
                        parent.left = current.right;
                    }
                    else if (parent) {
                        parent.right = current.right;
                    }
                    else {
                        // No parent, this must be the root node.
                        tree = current.right;
                    }
                }
                else {
                    // Node has 2 children.
                    // First, find the minimum element in the right subtree of the node to be removed.
                    var minNode = current.right;
                    while (minNode) {
                        if (minNode.left) {
                            minNode = minNode.left;
                        }
                        else {
                            // We're at the bottom of the subtree.
                            break;
                        }
                    }
                    
                    // Delete minNode.
                    current = treeDeletion(current, minNode.value);

                    // Replace value.
                    current.value = minNode.value;
                }
                break;
            }
            else if (key < current.value) {
                current = current.left;
            }
            else if (key > current.value) {
                current = current.right;
            }
        }
    }

    return tree;
};