Hi,

If I have 2 binary trees that are sorted (meaning the left subtree contains nodes smaller that it's parent, while the right subtree contains larger nodes). Let's say the nodes contain an integer.

How would I write a function to merge the two trees?

The way I was thinking was

1) traverse one of the trees using in-order traversal (meaning left node, then root node, then right node)

2) For each node in this tree, I would call an insert method that would insert this node into the other tree.

I guess this would work but is there are better way? Would it be possible somehow to insert more than 1 node at a time (because the tree being traversed is also sorted)?

Any ideas to accomplish this using a good algorithm would be appreciated.

Thanks

AJ

Tree 2 Inserted Into Tree 1:

2

/ \

1 10

4

/ \

3 6

will Become

2

/ \

1 10

/ \

3

\

4

\

6

If you notoce, since the resulting tree retains the same structure, the inserted tree will just be tacked on the end of one of the lists and the tree becomes unbalanced. The tree will start to degrade into a Linked List. What you want to have happen is something like this:

1) The Median of tree 1 is 2

2) The Median of tree 2 is 4

(assuming both trees are balanced)

3) The MIN/MAX of tree 1 is 1,10

4) The MIN/MAX of tree 2 is 3,6

4.5-The Min/Max of both trees is 1 and 10

5) Choose a new root as 4 because 4 is closest to the middle of 10 and 1

(You could get more complex here and find the closed number between (MIN-MAX)/2=(10-1)/2=9/2=4

6) Iterate through BOTH trees using a PREFIX iterator (in other words visit the nodes 1st then visit the children)

Create a new tree with 4 as the root

Insert 2

Insert 3

Insert 1

Insert 10

Insert 6

The resulting tree is:

4

/ \

2 10

/ \ /

1 3 6

Another implementation of a tree is called a red-black tree (used by java.util.TreeMap) which automatically rebalances the tree after EVERY insert. This guarantees that the tree is always balanced which is most efficient for searching.