CareerCup

O(log n) is possible.

Split and join can be implement in O(log n) for AVL, red-black and variants.

//merge two BST into a balanced tree time O(n+m) space O(1)
//12345678
//          5   
//      3      7
//    2  4  6  8
//  1
public static class TreeNode {
 TreeNode left;
 TreeNode right;
 int data;
}

public TreeNode mergeTrees(TreeNode rootA, TreeNode rootB) {
 TreeNode sortedListA = treeToList(rootA, null);
 TreeNode sortedListB = treeToList(rootB, null);
 int[] refSize = new int[] {0}; // cheat for reference
 TreeNode mergedLists = mergeList(sortedListA, sortedListB, refSize);
 return sortedListToBST(new TreeNode[] {mergedLists}, 0, refSize[0]);
}

//return balanced BST
private TreeNode sortedListToBST(TreeNode[] refSortedList, int startIdx, int endIdx) {
 TreeNode root = null;

 if (startIdx < endIdx) {
  int midIdx = (startIdx + endIdx) >> 1;
  
  TreeNode left = sortedListToBST(refSortedList, startIdx, midIdx);
  root = refSortedList[0];
  root.left  = left;
  refSortedList[0] = refSortedList[0].right;
  root.right = sortedListToBST(refSortedList, midIdx, endIdx);
 }
 
 return root;
}

private TreeNode treeToList(TreeNode tree, TreeNode head) {
 if (tree == null)
  return head;

 TreeNode left = treeToList(tree.left, head);
 tree.left = left;
 
 return treeToList(tree.right, tree);
}

private TreeNode mergeList(TreeNode listA, TreeNode listB, int[] size) {
 TreeNode result = null;

 while (listA != null || listB != null) {
  size[0]++;

  if (listA == null) {
   result = addNodeToList(result, listB);
   listB = nextNode(listB, true);
  } else if (listB == null) {
   result = addNodeToList(result, listA);
   listA = nextNode(listA, true);
  } else {
   if (listA.data > listB.data) {
    result = addNodeToList(result, listA);
    listA = nextNode(listA, true);
   } else {
    result = addNodeToList(result, listB);
    listB = nextNode(listB, true);
   } 
  }
 }
return result;
}

private TreeNode addNodeToList(TreeNode list, TreeNode newNode) {
 if (list == null)
  return newNode;

  newNode.right = list.right;
  list.right = newNode;
  return list;
 }

private TreeNode nextNode(TreeNode list, boolean unlink) {
 TreeNode result = list.left;

 if (unlink)
  list.left = null;

 return result;
}

Apart from solutions using linked list if u know any thing tell me...

no

sd

This is some approach:

void insert(struct node* tree1, struct node* tree2) {
// remember the left and right sub-trees;
struct node* left = tree2->left;
struct node* right = tree2->right;
insertintoTree(struct node* tree1, tree2);
insertintoTree(struct node* tree1, left);
insertintoTree(struct node* tree1, right);
}
insertintoTree() {
// normal binary tree approach to insert into a balanced tree;
}

pseodo code:
merging B in A.

void merge(rootA, rootB)
{
    merge(rootA,rootB->left);
    merge(rootA,rootB->right);
    mergeAndBalance(rootA,rootB);
}
void mergeAndBalance(rootA,rootB)
{
    rootB->left=rootB->right=NULL;
    /*insert rootB and balance the tree using rotations
      lot of code already available. 
    */
}

1) Two sorted arrays, just merge them to a 3rd sorted array using the merge routine from mergesort.
2) pass the combined sorted array into a method that will build the tree in a binary search fashion (ie, divide the sorted array in half, left side of the array will be the left side of the tree, right side of the array will be the right side of the tree).

<pre lang="" line="1" title="CodeMonkey20921" class="run-this">See my reply above:

public void buildTree(TreeNode[] nodes, int low, int high)
{
if (low > high)
return;

int mid = (low + high) / 2;

insert(nodes[mid]);
buildTree(nodes, low, mid-1);
buildTree(nodes, mid+1, high);
}

public void insert(TreeNode n)
{
if (root == null)
root = new TreeNode(n.data);
else
{
TreeNode curr = root;
TreeNode parent = curr;
boolean addingAsLeftChild = false;

while (true)
{
if (n.data > curr.data)
{
parent = curr;
curr = curr.right;
addingAsLeftChild = false;
}
else if (n.data < curr.data)
{
parent = curr;
curr = curr.left;
addingAsLeftChild = true;
}
else
{
//duplicates not allowed
return;
}

if (curr == null)
{
if (addingAsLeftChild)
{
parent.left = new TreeNode(n.data);
}
else
{
parent.right = new TreeNode(n.data);
}
return;
}
}
}
}
</pre><pre title="CodeMonkey20921" input="yes">
</pre>

yo just convert both bsts to the DLLs in linear time and then merge the two linked list aagaina linerar time and then convert this dll to a bst again a linear time a nd constant space taken

a) Find the number of nodes in each tree. treeA (n1), treeB (n2)
b) Find min(treeA), max(treeA), min(treeB), max(treeB) {O(n1 + n2) Worst case)}
c) The root of the merged tree, should be such that if n1 and n2 values were to be arranged in asc order, then root will be at index (n1+n2)/2 (To ensure it is balanced)
Using the info in step 1 and 2, we can find which tree this newRoot will lie in , and we can also find the node.

4) Delete this node from the tree. (O(log n)

5) Now traverse treeA in post order, delete the node from treeA, by setting the node's left and right pointers to null. Add it in the tree with the root as newRoot.
(Pls note that we are not creating any new node, but only changing pointers

6) do the same with treeB

Complexity: O((n1 + n2) log(n1 + n2))
worst case (O (n1 + n2)^2)

Constant space

As pointed out in the question, n1 and n2 are not needed to be equal. they can as well be different

1)Serialize both trees
2)Merge sort
3)Convert Merged Doubly Linked List to a Balanced BST

Don't we need to just insert the root of tree A in tree B?

The best you can do is to traverse both the trees inorder and store them into arrays and then merge them.