#codingexercise

Merge two Binary Search Trees(BST)

Node Merge(Node tree1, Node tree2)

{

var in1 = new List<int>();

InOrder(Node tree1, ref in1);

var in2 = newList<int>();

InOrder(Node tree2, ref in2);

var result = in1.Merge(in2);

return ToBST(result, 0, result.count-1);

}

void InOrder (Node root, List<int> tree)

{

if (root == null) return;

InOrder(root.left);

tree.add(root.data);

InOrder(root.right);

}

Node ToBST(List<int> nums, int start, int end)

{

if (start > end) return null;

int mid = (start + end) / 2;

var root == new Node();

root.data = nums[mid];

root.left = ToBST(nums,start, mid-1);

root.right = ToBST(nums, mid+1, end);

return root;

}

Another method to do this is to use two auxiliary stacks for two BSTs.  If we get a element smaller from the trees, we print it. If the element is greater, we push it to the stack for the next iteration.

We use the iterative inorder traversal :

-          Create an empty stack S

-          Initialize current node as root

-          Push the current node to stack S, set current to current.left, until current is NULL

-          If the current is null and stack is not empty then

o   Pop the top item from stack

o   Print the popped item

o   Set current = popped_item.right

o   Goto step 3

-          If current is null and the stack is empty, then we are done.

To merge the BST we do the following:

Initialize two stacks s1 and s2 from null.

If the first tree is null, do iterative inorder traversal of second to print the merge

If the second tree is null, do iterative inorder traversal of first to print the merge

Set current in tree 1 to be cur1 and current in tree 2 to be cur2

While either cur1 or cur 2 is not null or  one of the stacks is not empty:

-          If cur 1 or cur 2 is not null

o   For both the tree, if the current is not null, push it onto the stack, set current to current.left This will be repeated by the while until current is nul is null

-          Else

o   If either of the stacks is empty, then one tree is exhausted, print the other tree.  Do this for both stacks.

o   Set the current of each tree to the popped element from respective tree

o   Compare the two current and execute an iteration of step3 from iterative inorder traversal above  - the smaller of the two current nodes is printed, the larger pushed back on its corresponding stack

At the end of the while loop, both stacks should be empty and the currents must be pointing to null and both the trees would be printed.

There are other approaches possible:

1) Add the elements of one tree to the other one at a time by moving the root until there are no more nodes in the tree
2) Transform one of the trees into inorder and insert the items into the other tree.
3) Jointly traverse both trees to find the minimum in either tree, delete it and add to a new BST