## Amazon Interview Question

Software Engineers**Team:**Amazon Alexa

**Country:**United States

**Interview Type:**In-Person

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)

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

- M April 18, 2017