Union of Two Binary Search Trees

Question

I need some help figuring out how to merge two binary search trees. My idea/algorithm for this:

1) Make a new, third Binary search tree to keep the union of the other two trees.

2) Go through the first tree, copying all of its successive elements into the newly created tree.

3) Go through the second tree doing the same as above.

I have an add function which takes care of repetitions and putting stuff into the tree, so that part is not an issue. My problem is I don't know how to go through each of the nodes and manipulate them individually. I was thinking traversing the tree with something like:

public void inOrderTraverseTree(Node focusNode) {
        if (focusNode != null) {
             preorderTraverseTree(focusNode.leftChild);
             //this is where I can do an operation on the node
             preorderTraverseTree(focusNode.rightChild);

I'd like to take each successive node and add it to my third binary tree. As far as I can see, that's impossible to implement with any variation of the function above. Is there another way to go about this? Does it need a completely different algorithm?

Are the original BSTs balanced? Should the result be? – amit Mar 22 '15 at 19:02 — amit, Mar 22 '15 at 19:02

score 1 · Answer 1 · answered Mar 22 '15 at 19:51

Two binary search trees, B1 and B2 can be merged without using any new data structure/memory. We can do postorder traversal of 1 tree, say B1, deleting its nodes one by one and inserting them into the other tree B2.

By this approach, B2 will contain all the nodes of original B1 and B2 and B1 will have been deallocated in the same process.

Union of Two Binary Search Trees

1 Answers1