CareerCup

This can be done in 3 steps:
1. covert the BSTs to sorted linked list (this can be done in place with O(m+n) time)
2. Merge this two sorted linked lists to a single list (this can be done in place with O(m+n) time)
3. Convert sorted linked list to balanced BST (this can be done in place with O(m+n) time)

The output here is missing 110. The output should be:
90 (60 (5)(70)) (110 () (800)).

Looks like a tree rotation problem to handle balancing, just as in AVL trees.

. convert bst to linkedlist
merge 2 sorted lists
convert list to bst

// use morris trasversal. and in-place.. and but won't be O(m+n).

/**
Tree1: 90
/ \
70 110

Tree2: 60
/ \
5 800

Balanced Tree3:
70
/ \
5 110
\ / \
60 90 800
*/
Java language solution of this problem is given below:

/**
 * Solution:
 * 1. Covert the BSTs to sorted linked list (using inorder traversal, Time O(m+n))
 * 2. Merge this two sorted linked lists to a single list (same as merge portion of merge sort, Time O(m+n))
 * 3. Convert sorted linked list to balanced BST (this can be done in place with O(m+n) time)
 */
import java.util.ArrayList;
import java.util.List;

public class MergeTwoBST {
	
	class TreeNode {
		private int value;
		private TreeNode leftNode;
		private TreeNode rightNode;
	
		public TreeNode(int value) {
			super();
			this.value = value;
		}
		public int getValue() {
			return value;
		}
		public void setValue(int value) {
			this.value = value;
		}
		public TreeNode getLeftNode() {
			return leftNode;
		}
		public void setLeftNode(TreeNode leftNode) {
			this.leftNode = leftNode;
		}
		public TreeNode getRightNode() {
			return rightNode;
		}
		public void setRightNode(TreeNode rightNode) {
			this.rightNode = rightNode;
		}
	}

	public static TreeNode mergeBSTToFormBalancedTree(TreeNode tree1, TreeNode tree2){
		if(tree1 != null && tree2 != null){
			List<Integer> sortedList1 = new ArrayList<Integer>();
			List<Integer> sortedList2 = new ArrayList<Integer>();
			getSortedList(tree1, sortedList1);
			getSortedList(tree2, sortedList2);
			List<Integer> sortedList3 = merge(sortedList1, sortedList2);
			return createTree(sortedList3, 0, sortedList3.size() - 1);
		}
		else if(tree1 != null){
			return tree1;
		}
		else if(tree2 != null){
			return tree2;
		}
		return null;
	}
	
	// left, root, right( INORDER TRAVERSAL GIVES SORTED ORDER)
	private static void getSortedList(TreeNode node, List<Integer> sortedList){
		if(node != null){
			getSortedList(node.getLeftNode(), sortedList);
			sortedList.add(node.getValue());
			getSortedList(node.getRightNode(), sortedList); 
		}
	}
	
	private static List<Integer> merge(List<Integer> sortedList1, List<Integer> sortedList2){
		List<Integer> mergeList = new ArrayList<Integer>(sortedList1.size() + sortedList2.size());
		int index1 = 0, index2 = 0;
		while(index1 < sortedList1.size() && index2 < sortedList2.size()){
			if(sortedList1.get(index1) <= sortedList2.get(index2)){
				mergeList.add(sortedList1.get(index1));
				index1++;
			} else {
				mergeList.add(sortedList2.get(index2));
				index2++;
			}
		}
		while(index1 < sortedList1.size()){
			mergeList.add(sortedList1.get(index1));
			index1++;
		}
		while(index2 < sortedList2.size()){
			mergeList.add(sortedList2.get(index2));
			index2++;
		}
		return mergeList;
	}
	
	// Create Tree using array
	private static TreeNode createTree(List<Integer> data, int begin, int end) {
		if (begin > end) {
			return null;
		}
		if (begin == end) {
			return new TreeNode(data.get(begin));
		}
		int size = end - begin + 1;
		int lSize = (size - 1) >> 1;
		TreeNode parent = new TreeNode(data.get(begin + lSize));
		parent.setLeftNode(createTree(data, begin, begin + lSize - 1));
		parent.setRightNode(createTree(data, begin + lSize + 1, end));
		return parent;
	}

	public static void printLevelWiseTree(List<TreeNode> nodes) {
		if(nodes == null || nodes.isEmpty()){
			return;
		}
		else{
			List<TreeNode> next = new ArrayList<TreeNode>(); 
		    for(TreeNode node : nodes) {
		        System.out.print(node.getValue()+" ");
		    	if(node.getLeftNode() != null){
		    		next.add(node.getLeftNode());
		    	}
		    	if(node.getRightNode() != null){
		    		next.add(node.getRightNode());
		    	}
		    }
		    System.out.println();
		    printLevelWiseTree(next);	
		}
	}

	public static void main(String[] args) {
		TreeNode tree1 = new TreeNode(90);
		tree1.setLeftNode(new TreeNode(70));
		tree1.setRightNode(new TreeNode(110));
		
		TreeNode tree2 = new TreeNode(60);
		tree2.setLeftNode(new TreeNode(5));
		tree2.setRightNode(new TreeNode(800));
		
		TreeNode balancedTree = mergeBSTToFormBalancedTree(tree1, tree2);
		List<TreeNode> list = new ArrayList<TreeNode>();
		list.add(balancedTree);
		printLevelWiseTree(list);
	}
}

output :-->           
                     70
 	 	     /   \
                   60     90
                  /         \
                 5           800

sorry , output tree is not clear in que due to error in que box.

This is a solution with time complexity of O((m + n)*log min(n,m)) and constant space complexity. If min(m,n) << m+n, we might say that this is O(m+n). If someone can optimize this to get an O(m+n) solution (without the log min(n,m)) with constant space, I would be curious to hear the solution. The assumption here is that since the question requires using no extra space, we need to modify the existing trees to derive our merged tree. We use the algorithm in a recursive fashion to arrive at our final merged tree :-
1. First traverse all the elements to find the center element of the m+n elements. So, if this were an m+n sized array, we would be looking for the (m+n/2)th element if m+n is odd OR the ((m+n)/2 + 1)th element if m+n is even. This is because if there are even number of elements, the balance binary trees right subtree would have one element less than the left subtree.
This is our first (m+n)th traversal while tracking time complexity and thus far we have not used any extra space.
2. Next choose the bst which contains the the element that we found in step 1, and modify it so that this element becomes the root. Again, we use no extra space, and this is an O(n) or O(m) time complexity operation.
3. Now add a node to the other tree with the same value as the root of the other tree, and modify this tree to make this node the root node. Again an O(m) or O(n) operation in terms of time complexity, and one node extra in terms of space complexity.
4. Now choose the tree with fewer nodes, and free the root node, after holding pointers/references to the left and right subtrees - Let us call the resultant trees from this operation the left main bst and right main bst.
5. (recursion)
a. final_root = root
b. merge left main bst with the left subtee of the other tree
c. merge right main bst with the right subtree of the other tree
6.
if (final_root != null)
a. final_root->left = root of left merge
b. final_root->right = root of right merge
else
return final_root

1)Get a sorted linked list out of the two trees.
a) Create first sorted list by Inorder traversal on first tree
b) Create Second sorted list by Inorder traversal on first tree
c) Merge two sorted list.
Or
a) Inorder traversal of both trees together to create single sorted merged list.(Do inorder on first and second, stop first till the time second is smaller and viceversa)
Complexity: O(m+n)
2)Build balanced binary tree out of sorted linked list.
Complexity: O(m+n)
Hint: Middle element is root of balanced btree

Convert two trees in DoubleyLinkedlist using inorder traversal then merge them thus you will have a sorted list now make a tree out of it using recursive procedure using divide and conquer will result in a balanced binary search tree.

Find min in left subtree(call this modified subtree T1), Find max in right subtree(T2)
Make T1 the left child of T2

Note: since the input trees are already balanced, the generated tree should also be balanced, similar trick is used in splay trees

Balance Tree 1 using rotations. I believe this is O(log n) if doing log n rotations and each rotation is constant time.
Insert nodes of Tree 2 in a preorder fashion into Tree 1. O(m) to traverse + O(log n) to insert.

1) Remove each element from BST-2 and add it to BST-1. So the space which was being used for BST-2 is free now.
2) Remove each element from BST-1 and make a balanced tree (Red-Black/AVL) out of it.

In this way extra space won't be utilized. The space will be utilized only after making that space free from the other tree.

Time Complexity = O(log(m+n))

Please give suggestions.

Once recursion is used, the space complexity will be O(h) with h=tree height since you need to consider the stack of function recursion, right?