Merge 2 BSTs into single height balanced BST.

Given a two balanced binary search trees.Merge both the trees so that it will form again a balanced binary search tree.
(NOTE: Should the input bst s have same number of nodes? if the input bst s have unequal nodes, we cant necessarily build a balanced bst for the result)


Approach:


Using extra space:
1)Serialize both trees - take inorder traversals in arrays A and B.
2)Merge A and B into array C (this array is not sorted with elements from both A and B)
3) construct BST from C by taking the mid as root and recursilvely constructing the left subtree and right subtree.




Without using extra space:
1. Convert binary search trees A and B into doubly link list inplace.
2. merge sort both double linklists A and B say C.
3. construct BST from doubly link list C. 


Node dllToBST(Node node) {
if (null == node) { return node; }
Node mid = getMidNode(node);
mid.left.next = null; mid.right.prev = null;
mid.left = dllToBST(node);
mid.right = dllToBST(mid.right);

return mid;
}


Node getMidNode(Node node) {
//take 2 ptrs p1 and p2 both starting at node.
// run p2 twice as fast as p1 and then p2 reaches the end, p1 would be pointing to the mid of the doubly link list.
}