The first of your problems, namely code duplication is stemmed from the wrong interface. exists_helper returning a boolean violates a very important (and unfortunately little known) principle: do not throw away the information you computed. In case of exists_helper computed is an insertion point for the value you did not find. Returning that makes insert_helper, and the find, and deletethin wrappers aroundexists_helper`.

Along the same line, insert shall return an indication of success/failure along with the node itself, STL style. It doesn't really matter in case of integers, but for more complex ValueType we are usually interested in what did prevent insertion.

I don't approve recursive nature of exists and insert. They are tail recursive, and better be written as iterative.

Regarding deletion, I think you over engineered it. Consider a pseudocode:

    if left child exists,
        find the rightmost descendant
        rightmost descendant's->right = right child
        return left child as new root
    else
        return right child as new root

Note that your case 2 doesn't need to be special cased: left child itself is the rightmost descendant.

The first of your problems, namely code duplication is stemmed from the wrong interface. exists_helper returning a boolean violates a very important (and unfortunately little known) principle: do not throw away the information you computed. In case of exists_helper computed is an insertion point for the value you did not find. Returning that makes insert_helper, and the find, and delete thin wrappers around exists_helper.

Along the same line, insert shall return an indication of success/failure along with the node itself, STL style. It doesn't really matter in case of integers, but for more complex ValueType we are usually interested in what did prevent insertion.

I don't approve recursive nature of exists and insert. They are tail recursive, and better be written as iterative.

Regarding deletion, I think you over engineered it. Consider a pseudocode:

    if left child exists,
        find the rightmost descendant
        rightmost descendant's->right = right child
        return left child as new root
    else
        return right child as new root

Note that your case 2 doesn't need to be special cased: left child itself is the rightmost descendant.

The first of your problems, namely code duplication is stemmed from the wrong interface. exists_helper returning a boolean violates a very important (and unfortunately little known) principle: do not throw away the information you computed. In case of exists_helper computed is an insertion point for the value you did not find. Returning that makes insert_helper a thin wrapper around exists_helper.

Along the same line, insert shall return an indication of success/failure along with the node itself, STL style. It doesn't really matter in case of integers, but for more complex ValueType we are usually interested in what did prevent insertion.

I don't approve recursive nature of exists and insert. They are tail recursive, and better be written as iterative.

Regarding deletion, I think you over engineered it. Consider a pseudocode:

    if left child exists,
        find the rightmost descendant
        rightmost descendant's->right = right child
        return left child as new root
    else
        return right child as new root

Note that your case 2 doesn't need to be special cased: left child itself is the rightmost descendant.

The first of your problems, namely code duplication is stemmed from the wrong interface. exists_helper returning a boolean violates a very important (and unfortunately little known) principle: do not throw away the information you computed. In case of exists_helper computed is an insertion point for the value you did not find. Returning that makes insert_helper, and the find, and deletethin wrappers aroundexists_helper`.

Along the same line, insert shall return an indication of success/failure along with the node itself, STL style. It doesn't really matter in case of integers, but for more complex ValueType we are usually interested in what did prevent insertion.

I don't approve recursive nature of exists and insert. They are tail recursive, and better be written as iterative.

Regarding deletion, I think you over engineered it. Consider a pseudocode:

    if left child exists,
        find the rightmost descendant
        rightmost descendant's->right = right child
        return left child as new root
    else
        return right child as new root

Note that your case 2 doesn't need to be special cased: left child itself is the rightmost descendant.