Вставка двоичного дерева (в порядке сортировки)

Я искал в Интернете помощь по этой проблеме, но мне нужна помощь. Это не совсем обычная проблема вставки для бинарного дерева, поскольку мы не можем работать непосредственно с самой структурой дерева. Мой профессор написал это сам и дал нам функции, которые мы можем использовать для написания функций, относящихся к бинарным деревьям. Таким образом, я не могу использовать узлы, указатели и прочее. Также это на С++.

Так или иначе, вот описание рекурсивной функции, которую я должен написать (вместе с моей начальной попыткой работы с проблемой). Обратите внимание, что он полностью возвращает новое дерево, фактически ничего не добавляя к существующему дереву.

tree_t insert_tree(int elt, tree_t tree)
{
    /* 
    // REQUIRES; tree is a sorted binary tree
    // EFFECTS: returns a new tree with elt inserted at a leaf such that 
    //          the resulting tree is also a sorted binary tree.
    //
    //          for example, inserting 1 into the tree:
    //
    //                           4
    //                         /   \
    //                        /      \
    //                       2        5
    //                      / \      / \
    //                         3 
    //                        / \
    //
    // would yield
    //                           4
    //                         /   \
    //                        /      \
    //                       2        5
    //                      / \      / \
    //                     1   3 
    //                    / \ / \
    // 
    // Hint: an in-order traversal of a sorted binary tree is always a
    //       sorted list, and there is only one unique location for
    //       any element to be inserted.
    */

if (elt < elt(tree_left(tree)){
    return insert_tree(tree_left(left));
} else {
    return insert_tree(tree_right(right));
}
}

И вот функции, которые мы можем использовать:

extern bool tree_isEmpty(tree_t tree);
    // EFFECTS: returns true if tree is empty, false otherwise

extern tree_t tree_make();
    // EFFECTS: creates an empty tree.

extern tree_t tree_make(int elt, tree_t left, tree_t right);
    // EFFECTS: creates a new tree, with elt as it's element, left as
    //          its left subtree, and right as its right subtree

extern int tree_elt(tree_t tree);
    // REQUIRES: tree is not empty
    // EFFECTS: returns the element at the top of tree.

extern tree_t tree_left(tree_t tree);
    // REQUIRES: tree is not empty
    // EFFECTS: returns the left subtree of tree

extern tree_t tree_right(tree_t tree);
    // REQUIRES: tree is not empty
    // EFFECTS: returns the right subtree of tree

extern void tree_print(tree_t tree);
    // MODIFIES: cout
    // EFFECTS: prints tree to cout.