https://chikuwa-tech-study.blogspot.com/2021/06/java-binary-search-tree.html

BinarySearchTree.java

public class BinarySearchTree {
    private TreeNode<Integer> rootNode;

    public void init(int[] values) {
        if (values.length == 0) {
            return;
        }

        TreeNode<Integer> visitedNode;
        this.rootNode = new TreeNode<>(values[0]);
        for (int i = 1; i < values.length; i++) {
            visitedNode = this.rootNode;
            TreeNode<Integer> newNode = new TreeNode<>(values[i]);

            while (true) {
                if (values[i] < visitedNode.getValue()) {
                    if (visitedNode.getLeftNode() == null) {
                        visitedNode.setLeftNode(newNode);
                        break;
                    }
                    visitedNode = visitedNode.getLeftNode();
                } else {
                    if (visitedNode.getRightNode() == null) {
                        visitedNode.setRightNode(newNode);
                        break;
                    }
                    visitedNode = visitedNode.getRightNode();
                }
            }
        }
    }

    public Integer find(int target) {
        if (this.rootNode == null) {
            return null;
        }

        StringBuilder sb = new StringBuilder()
                .append("Searching path of ")
                .append(target)
                .append(": Root");

        TreeNode<Integer> visitedNode = this.rootNode;
        while (visitedNode.getValue() != target) {
            if (target < visitedNode.getValue()) {
                visitedNode = visitedNode.getLeftNode();
                sb.append(" -> Left");
            } else {
                visitedNode = visitedNode.getRightNode();
                sb.append(" -> Right");
            }

            if (visitedNode == null) {
                return null;
            }
        }

        System.out.println(sb);
        return visitedNode.getValue();
    }

    public void remove(int target) {
        if (this.rootNode == null) {
            return;
        }

        TreeNode<Integer> parentOfRemovingNode = null;
        TreeNode<Integer> removingNode = this.rootNode;
        boolean isLeftNode = false;
        while (removingNode.getValue() != target) {
            parentOfRemovingNode = removingNode;
            if (target < removingNode.getValue()) {
                removingNode = removingNode.getLeftNode();
                isLeftNode = true;
            } else {
                removingNode = removingNode.getRightNode();
                isLeftNode = false;
            }

            if (removingNode == null) {
                return;
            }
        }

        if (removingNode.getLeftNode() == null && removingNode.getRightNode() == null) {
            removeLeafNode(parentOfRemovingNode, isLeftNode);
        } else if (removingNode.getLeftNode() == null ^ removingNode.getRightNode() == null) {
            removeNodeHavingOneChild(parentOfRemovingNode, isLeftNode);
        } else {
            removeNodeHavingTwoChild(parentOfRemovingNode, isLeftNode);
        }
    }

    private void removeLeafNode(TreeNode<Integer> parentOfRemovingNode, boolean isLeftNode) {
        if (parentOfRemovingNode == null) {
            this.rootNode = null;
        } else if (isLeftNode) {
            parentOfRemovingNode.setLeftNode(null);
        } else {
            parentOfRemovingNode.setRightNode(null);
        }
    }

    private void removeNodeHavingOneChild(TreeNode<Integer> parentOfRemovingNode, boolean isLeftNode) {
        if (parentOfRemovingNode == null) {
            this.rootNode = isLeftNode
                    ? this.rootNode.getLeftNode()
                    : this.rootNode.getRightNode();
            return;
        }

        TreeNode<Integer> removingNode = isLeftNode
                ? parentOfRemovingNode.getLeftNode()
                : parentOfRemovingNode.getRightNode();
        TreeNode<Integer> replacingNode = removingNode.getLeftNode() != null
                ? removingNode.getLeftNode()
                : removingNode.getRightNode();

        if (isLeftNode) {
            parentOfRemovingNode.setLeftNode(replacingNode);
        } else {
            parentOfRemovingNode.setRightNode(replacingNode);
        }
    }

    private void removeNodeHavingTwoChild(TreeNode<Integer> parentOfRemovingNode, boolean isLeftNode) {
        TreeNode<Integer> removingNode;
        if (parentOfRemovingNode == null) {
            removingNode = this.rootNode;
        } else {
            removingNode = isLeftNode
                    ? parentOfRemovingNode.getLeftNode()
                    : parentOfRemovingNode.getRightNode();
        }

        boolean isRemovingNodeHasRightNode = removingNode.getRightNode() != null;
        TreeNode<Integer> parentOfReplacingNode;
        TreeNode<Integer> replacingNode;
        if (isRemovingNodeHasRightNode) {
            parentOfReplacingNode = findParentOfMinInRightTree(removingNode);
            replacingNode = parentOfReplacingNode == removingNode
                    ? removingNode.getRightNode()
                    : parentOfReplacingNode.getLeftNode();
        } else {
            parentOfReplacingNode = findParentOfMaxInLeftTree(removingNode);
            replacingNode = parentOfReplacingNode == removingNode
                    ? removingNode.getLeftNode()
                    : parentOfReplacingNode.getRightNode();
        }

        if (parentOfReplacingNode != removingNode) {
            if (isRemovingNodeHasRightNode) {
                parentOfReplacingNode.setLeftNode(replacingNode.getRightNode());
            } else {
                parentOfReplacingNode.setRightNode(replacingNode.getLeftNode());
            }
        }
        replacingNode.setLeftNode(removingNode.getLeftNode());
        replacingNode.setRightNode(removingNode.getRightNode());

        if (parentOfRemovingNode == null) {
            this.rootNode = replacingNode;
        } else {
            if (isLeftNode) {
                parentOfRemovingNode.setLeftNode(replacingNode);
            } else {
                parentOfRemovingNode.setRightNode(replacingNode);
            }
        }
    }

    private TreeNode<Integer> findParentOfMaxInLeftTree(TreeNode<Integer> node) {
        TreeNode<Integer> parentNode = node;
        TreeNode<Integer> visitedNode = node.getLeftNode();
        while (visitedNode.getRightNode() != null) {
            parentNode = visitedNode;
            visitedNode = visitedNode.getRightNode();
        }

        return parentNode;
    }

    private TreeNode<Integer> findParentOfMinInRightTree(TreeNode<Integer> node) {
        TreeNode<Integer> parentNode = node;
        TreeNode<Integer> visitedNode = node.getRightNode();
        while (visitedNode.getLeftNode() != null) {
            parentNode = visitedNode;
            visitedNode = visitedNode.getLeftNode();
        }

        return parentNode;
    }

}

TreeNode.java

public class TreeNode<E> {
    private E value;
    private TreeNode<E> leftNode;
    private TreeNode<E> rightNode;

    public TreeNode(E value) {
        this.value = value;
    }

    public E getValue() {
        return value;
    }

    public TreeNode<E> getLeftNode() {
        return leftNode;
    }

    public void setLeftNode(TreeNode<E> leftNode) {
        this.leftNode = leftNode;
    }

    public TreeNode<E> getRightNode() {
        return rightNode;
    }

    public void setRightNode(TreeNode<E> rightNode) {
        this.rightNode = rightNode;
    }

    @Override
    public String toString() {
        return value.toString();
    }
}