Posted on 2004-10-10
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.