insert all elements from one binary search tree into another-CodePudding

I am given two binary search trees, and I need to insert all the nodes of the binary search tree with the smaller height into the other tree. Both trees are self balancing.

I am not allowed to flatten the trees into sorted arrays.

I am struggling to write a function for this. What I have so far does not seem to work:

void merge(struct node* tree1, struct node *tree2)
{   
    if (tree1 != NULL) {
        merge(tree1->left_node, tree2);
        insert(tree2, tree1->value);
        merge(tree1->right_node, tree2);
    }
     
}

assume insert(struct node * node, int value) is a function that inserts nodes with values into a self balancing binary search tree.

this is how the tree is implemented:

struct node {
    int value;           
    struct node *left_node;  
    struct node *right_node; 
    int height;

};

CodePudding user response：

If insert rebalances the tree, it may select a different node as the root. There are two main ways to deal with that. One way is to use a double pointer for the destination tree in both insert and merge like this:

void insert(struct node **tree, int value)
{
    /* TO BE IMPLEMENTED */
    /* MAY UPDATE *tree */
}

void merge(struct node *tree1, struct node **tree2)
{   
    if (tree1 != NULL) {
        merge(tree1->left_node, tree2);
        insert(tree2, tree1->value);
        merge(tree1->right_node, tree2);
    }
}

The other main way is for both insert and merge to return the newly selected node of the destination tree like this:

struct node *insert(struct node *tree, int value)
{
    /* TO BE IMPLEMENTED */
    /* MAY UPDATE tree */
    return tree; /* return updated root */
}

struct node *merge(struct node *tree1, struct node *tree2)
{   
    if (tree1 != NULL) {
        tree2 = merge(tree1->left_node, tree2);
        tree2 = insert(tree2, tree1->value);
        tree2 = merge(tree1->right_node, tree2);
    }
    return tree2; /* return updated root */
}

There are a couple of other ways to do it that are a mixture of the main two methods above. One of the two functions insert and merge could use a double pointer and the other one could return the newly selected node. For example:

struct node *insert(struct node *tree, int value)
{
    /* TO BE IMPLEMENTED */
    /* MAY UPDATE tree */
    return tree; /* return updated root */
}

void merge(struct node *tree1, struct node **tree2)
{   
    if (tree1 != NULL) {
        *tree2 = merge(tree1->left_node, *tree2);
        *tree2 = insert(*tree2, tree1->value);
        *tree2 = merge(tree1->right_node, *tree2);
    }
}

Or:

void insert(struct node **tree, int value)
{
    /* TO BE IMPLEMENTED */
    /* MAY UPDATE *tree */
}

struct node *merge(struct node *tree1, struct node *tree2)
{   
    if (tree1 != NULL) {
        tree2 = merge(tree1->left_node, tree2);
        insert(&tree2, tree1->value);
        tree2 = merge(tree1->right_node, tree2);
    }
    return tree2; /* return updated root */
}