Algorithm for combining two binary trees?

Question

For example:

two trees:

8 9 5 7 4 20 30 

become one tree?

Answer 1

Without additional details / limitations, the easiest solution is to get the node leaf of any tree, delete it and use it as the root for the newly created three.

In your example:

  30 8 9 5 7 4 20 

This works because your trees do not seem to follow any particular order, do not seem balanced, and have no other restrictions.

Since any leaf node will do, it will be an O ( n ) operation in the worst case (go through one of the trees in any order until we meet the first leaf, delete it, add child links to both tree roots).

Answer 2

The easiest way to combine two binary trees is to iterate the left child of the same tree until reaching the node without the left child. Then add another root of the tree as the left child. The resulting tree for your example would be:

  8 5 7 9 4 20 30 

However, note how the resulting tree in this example is very unbalanced. This will lead to inefficient operations with the resulting tree, if that is the goal. The best solution is to evenly distribute nodes from the second tree to the first tree. One way to achieve this is to recursively add the root and left subtree of the second tree to the left subtree of the first tree, and the right subtree to the right subtree. To get a more even distribution, randomly choose which side to select the root at each step.

Please note that binary trees here are not binary search trees. Working with BST is a slightly more interesting case, since you must make sure that the resulting tree is also a valid BST. For those who are interested, here is a solution for this problem: finding the root value of tree 2 in tree 1. If we get to a dead end without finding this value, we can simply insert tree 2 in the place where this value will be in the tree . If we find the value, we can replace this node with tree 2. Then take the subtree rooted in the node that we are shifting and insert it into tree 2 using the same algorithm.

Answer 3

The main answer would be to simply add all the elements in the smaller tree to the larger tree.

Another option is to look at B-trees (trees balancing themselves)