CareerCup

Are they balanced? Are they binary search trees? Do you need to balance them?

If I take the question as it is, here is what I would do.

public static Node Merge(Node leftRoot, Node rightRoot)
{
	Node currentNode = leftRoot;
	while(currentNode.left != null)
	{
		currentNode = currentNode.left;
	}
	currentNode.left = rightRoot;
	return leftRoot;
}

Complexity : O(log(n)) + O(1).

Now, If there have preconditions such as the data should be merged one after another, like some sort of close merge, or if the tree is binary search tree. I would do the following.

public static Node Merge(Node leftRoot, Node rightRoot)
{
	Node leftList = CovertTreeToDoublyLinkedList(leftRoot);
	Node rightList = CovertTreeToDoublyLinkedList(rightRoot);
	// if the tree is BST, I will do the merging in sorted maner, and If it is just binary, I will put elements one after another.
	// I will consider BST 
	Node mergedList = MergeList(leftList, rightList);
	Node start = mergedList;
	Node end = mergedList;
	while(end.right != null)
	{
		end = end.right;
	}
	Node root = ConvertIntoTree(start, end);
	return root;
}


public static Node ConvertIntoTree(Node start, Node end)
{
	
	if(start.data > end.data)
	{
		return null;
	}
	if(start == end)
	{
		start.left = null;
		start.right = null;
		return start;
	}
	Node currentNode, nextNode;
	currentNode = start;nextNode = start;
	while(nextNode.right != null)
	{
		currentNode = currentNode.right;
		nextNode = nextNode.right.right;
	}
	currentNode.left = ConvertIntoTree(start, currentNode.left);
	currentNode.right = ConvertIntoTree(currentNode.right, right);
	return currentNode;
}

public static Node MergeList(Node left, Node right)
{
	if(left == null || right == null)
	{
		return left==null?right:left;
	}
	Node currentNode = left;
	while(true)
	{
		if(right == null)
		{
			while(left.left != null)
			{
				left = left.left;
			}
			return left;
		}
		if(currentNode.right == null)
		{
			currentNode.right = right;
			right.left = currentNode;
			while(left.left != null)
			{
				left = left.left;
			}
			return left;
		}
		if(currentNode.data < right.data)
		{
			currentNode = currentNode.right;
		}
		else
		{
			if(currentNode.left == null)
			{
				Node temp = right;
				right = right.right;
				temp.right = currentNode;
				currentNode.left = temp;
			}
			else
			{
				Node currentLeft = currentNode.left;
				currentLeft.right = right;
				right.left = currentLeft;
				currentNode.left = right;
				Node temp = right;
				right = right.right;
				temp.right = currentNode;
			}
		}
	}
}

public static Node CovertTreeToDoublyLinkedList(Node node)
{
	if(node.left != null)
	{
		Node temp = CovertTreeToDoublyLinkedList(node.left);
		temp.right = node;
		node.left = temp;
	}
	if(node.right != null)
	{
		Node temp = CovertTreeToDoublyLinkedList(node.right);
		node.right = temp;
		temp.left = node;
		while(node.right != null)
		{
			node = node.right;
		}
	}
	return node;
}

Complexity of this is O(n+m) + O(1).

class Solution(object):
    def mergeTrees(self, t1, t2):
        """
        :type t1: TreeNode
        :type t2: TreeNode
        :rtype: TreeNode
        """
        def helper(node1,p1,node2,side):
            if not node1 and not node2:
                return None
            
            elif node2 and not node1:
                if side =="right":
                    p1.right = node2
                else:
                    p1.left = node2
                return
                
            elif node1 and not node2:
                return 
            
            else:
                node1.val = node1.val + node2.val
                helper(node1.left,node1,node2.left,"left")
                helper(node1.right,node1, node2.right,"right")
        
        if not t1 and not t2:
            return None
        elif not (t1 and t2):
            return t1 or t2
        else:
            helper(t1,None,t2,None)
            return t1

I am assuming that the destination is a BST and it needs to be kept that way. My solution is below

void MergeTrees(Node firstTree, Node secondTree)
{
	if(secondTree.Left != null)
		MergeTrees(firstTree, secondTree.Left);
		
	if(secondTree.Right != null)
		MergeTrees(firstTree, secondTree.Right);
	
	secondTree.Left = null;
	secondTree.Right = null;
	InsertNode(firstTree, secondTree);
}

void InsertNode(Node destHead, Node sourceNode)
{
	if(destHead.Value > sourceNode.Value)
	{
		if(destHead.Left != null)
			InsertNode(destHead.Left, sourceNode);
		else
			destHead.Left = sourceNode;
	}
		
	if(destHead.Value < sourceNode.Value)
	{
		if(destHead.Right != null)
			InsertNode(destHead.Right, sourceNode);
		else
			destHead.Right = sourceNode;
	}
}

Complexity is O(n+m)

@sonesh Your first solution makes no sense whatsoever.

@Abcd I'm not sure how you arrived at the conclusion that your solution is O(n+m) when you're clearly doing m insertions into a BST of n elements.

Your solution is O(logn*m) if the first BST is balanced, O(n*m) otherwise.

7