Thread: Merging binaries trees into another one

Good evening. I'm studying merging of two binaries trees and I was concerned about two instructions:

Code:

bitree_root(merge)->left = bitree_root(left);
bitree_root(merge)->right = bitree_root(right);

I would like to know if merging two binaries trees means to create one of the subtrees as the left node of the new (merged) binary tree and the other as the right node of it.

Like this (please toggle to plain text):

Code:

        root of merged tree
           /             \ 
          /               \ 
left subtree           right subtree

Code:

 
int bitree_merge(BiTree *merge, BiTree *left, BiTree *right, const void
   *data) {

/*****************************************************************************
*                                                                            *
*  Initialize the merged tree.                                               *
*                                                                            *
*****************************************************************************/

bitree_init(merge, left->destroy);

/*****************************************************************************
*                                                                            *
*  Insert the data for the root node of the merged tree.                     *
*                                                                            *
*****************************************************************************/

if (bitree_ins_left(merge, NULL, data) != 0) {

   bitree_destroy(merge);
   return -1;

}

/*****************************************************************************
*                                                                            *
*  Merge the two binary trees into a single binary tree.                     *
*                                                                            *
*****************************************************************************/

bitree_root(merge)->left = bitree_root(left);
bitree_root(merge)->right = bitree_root(right);

/*****************************************************************************
*                                                                            *
*  Adjust the size of the new binary tree.                                   *
*                                                                            *
*****************************************************************************/

merge->size = merge->size + bitree_size(left) + bitree_size(right);

/*****************************************************************************
*                                                                            *
*  Do not let the original trees access the merged nodes.                    *
*                                                                            *
*****************************************************************************/

left->root = NULL;
left->size = 0;
right->root = NULL;
right->size = 0;

return 0;

}

If I was you, I would transform the trees to lists, then merge the lists and then back to BST's.

binary search tree (BST).

They seem ok, but you know that I can not really tell, aren't you?

People are commonly very relaxed with their terminology but there are "binary trees" where the nodes may be in any order, and "ordered binary trees" where an in-order traversal of the tree produces the items in sorted order.
If these are "ordered binary trees" then it is a case of going through one of the trees, possibly in a pre-order traversal, and inserting each node into the other tree, assuming you were to do it destructively.
However if you want a nicely balanced tree afterwards, the idea of transforming it into a list and then back into a fully balanced tree afterwards produces a good result. Much like the "scapegoat tree"

If they are not ordered, then how you do it is pretty much up to you, and whatever kind of result you want.