BinarySearchTree on deleteInternal and findMin has bug

[ac-tech-madcoz]

The following function has bug, which miss detecting when the node's left subtree has right subtree, the node's left subtree should be set to the node's left subtree's right subtree instead of setting nil.

Another problem is that when the deleted node's right subtree has no left subtree, then although the node's subtree is marked is deleted but it was not deleted when return, so after return the code should also check if the node's right subtree is marked deleted or not, if marked then set the node's right subtree to null to avoid missing deleting the node's right subtree.

The corrected function as follows:

    private void deleteInternal(BinarySearchTreeNode<K> node) {
        size--;
        // No children exist, mark this node as deleted
        if (!(node.leftExists() || node.rightExists())) {
            node.setDeleted(true);
            return;
        }

        // Only the left child exists, move the left node to this position
        if (node.leftExists() && !node.rightExists()) {
            node.setKey(node.getLeft().getKey());
            if (node.getLeft().rightExists()) {
                node.setRight(node.getLeft().getRight());
            }
            if (node.getLeft().leftExists()) {
                node.setLeft(node.getLeft().getLeft());
            } else {
                node.setLeft(null);
            }
            return;
        }

        // Only the right child exists, move the right node to this position
        if (node.rightExists() && !node.leftExists()) {
            node.setKey(node.getRight().getKey());
            if (node.getRight().leftExists()) {
                node.setLeft(node.getRight().getLeft());
            }
            if (node.getRight().rightExists()) {
                node.setRight(node.getRight().getRight());
            } else {
                node.setRight(null);
            }
            return;
        }

        // Both children exist, replace this node with with minimum node from
        // the right sub-tree
        K min = findMin(node.getRight());
        if(node.getRight().isDeleted()) {
            node.setRight(null);
        }
        node.setKey(min);
    }
    private K findMin(BinarySearchTreeNode<K> node) {
        if (!node.leftExists()) {
            if(!node.rightExists() {
                node.setDeleted(true);
            }
            return node.getKey();
        }

        K min = findMin(node.getLeft());
        if (node.getLeft().isDeleted()) {
            node.setLeft(null);
        } else {
            node.setLeft(node.getLeft().getRight());
        }
        return min;
    }