C/C++.BST-дерево.Операция объединения двух BST-деревьев

Нужно было реализовать объединение двух bst - деревьев по псевдокоду.

А это..как она собственно должна была осуществиться. Но что-то здесь явно не так..Хотя вроде вставка в корень и все ротации выполняются верно.Полагаю, что проблема именно в объединении. (k - это кол-во эл-тов поддерева каждого узда +1(т.е. сам узел тоже считается)) Была бы благодарна за помощь.

#include "stdio.h"
#include "stdlib.h"
#include "time.h"

typedef struct Node
{
    int data;
    int k;
    struct Node* left;
    struct Node* right;
} Node;

Node* createNode(int data)
{
    Node* node = (Node*) malloc(sizeof(Node));
    node->data = data;
    node->k = 1;
    node->left = NULL;
    node->right = NULL;
    return node;
}

void insert(Node** root,int key)
{
    if(*root == NULL)
    {
        *root = createNode(key);
        return;
    }

    (*root)->k++;
    if(key >= (*root)->data)
        insert(&(*root)->right,key);
    else 
        insert(&(*root)->left,key);
}

void print(Node* root)
{
    if(root == NULL) return;

    printf("%d(%d) ",root->data, root->k);
    print(root->left);
    print(root->right);
}

void rotateTreeLeft(Node** root)
{
    if(*root == NULL) return;
    if((*root)->right == NULL) return; 

    Node* x = (*root)->right;
    int k = (*root)->k;

    (*root)->right = x->left;
    x->left = *root;
    *root = x;

    (*root)->k = k;

    int pRootK = 0;    
    if((*root)->left->right != NULL) pRootK += (*root)->left->right->k;
    if((*root)->left->left != NULL) pRootK += (*root)->left->left->k;
    (*root)->left->k = 1 + pRootK;
}

void rotateTreeRight(Node** root)
{
    if(*root == NULL) return;
    if((*root)->left == NULL) return; 

    Node* x = (*root)->left;
    int k = (*root)->k;

    (*root)->left = x->right;
    x->right = *root;
    *root = x;

    (*root)->k = k;

    int pRootK = 0;
    if((*root)->right->right != NULL) pRootK += (*root)->right->right->k;
    if((*root)->right->left != NULL) pRootK += (*root)->right->left->k;
    (*root)->right->k = 1 + pRootK;
}

void insertRoot(Node** root,int key)
{
    if(*root == NULL)
    {
        *root = createNode(key);
        return;
    }

    (*root)->k++;
    if(key >= (*root)->data)
    {
        insert(&(*root)->right,key);
        rotateTreeLeft(root);
    }
    else 
    {
        insert(&(*root)->left,key);
        rotateTreeRight(root);
    }   
}

Node* Join(Node* a,Node* b)
{
    if(b == NULL) return a;
    if(a == NULL) return b;
    insertRoot(&b,a->data);
    b->left = Join(a->left, b->left);
    b->right = Join(a->right, b->right);
    delete a;
    return b;
}

int main()
{
    srand(37);

    int tree_size = 10;
    int i;
    //int* tree_arr = (int*) malloc(sizeof(int) * tree_size);

    
    /*for(i = 0; i < tree_size; i++)
    {
        tree_arr[i] = rand() % 30;
        printf("%d ",tree_arr[i]);
    }
    printf("\n");*/

    
    Node* root1 = NULL;
    Node* root2 = NULL;

    
    scanf("%d",&tree_size);
    for(i = 0; i < tree_size; i++)
    {
        int inp;
        scanf("%d",&inp);
        insert(&root1,inp);
    }
        

    scanf("%d",&tree_size);
    for(i = 0; i < tree_size; i++)
    {
        int inp;
        scanf("%d",&inp);
        insert(&root2,inp);
    }

    print(root1);
    printf("\n");
    //rotateTreeLeft(&root);
    print(root2);
    printf("\n");

    Node* root3 = Join(root1,root2);
    print(root3);
    printf("\n");

    
    //insertRoot(&root,rand() % 20);


    system("pause");
    return 0;
}

А это сам тест программы.Как и в примере.Но тут явно получилось..не как в примере.(4 по всей видимости стала корнем..хотя не должно было этого произойти)