Слияние двух двоичных деревьев поиска

Как объединить 2 дерева двоичного поиска таким образом, чтобы результирующее дерево содержало все элементы обоих деревьев, а также сохраняло свойство BST.

Я видел решение, представленное в. Как эффективно объединить два BST?

Однако это решение включает преобразование в двойной связный список. Мне стало интересно, есть ли более элегантный способ сделать это, который можно было бы реализовать на месте без преобразования. Я пришел к следующему псевдокоду. Работает ли он для всех случаев? Также у меня проблемы с 3-м случаем.

node* merge(node* head1, node* head2) {
        if (!head1)
            return head2;
        if (!head2)
            return head1;

        // Case 1.
        if (head1->info > head2->info) {
            node* temp = head2->right;
            head2->right = NULL;
            head1->left = merge(head1->left, head2);
            head1 = merge(head1, temp);
            return head1;
        } else if (head1->info < head2->info)  { // Case 2
            // Similar to case 1.
        } else { // Case 3
            // ...
        }
}