## Microsoft Interview Question for Interns

Country: United States

Comment hidden because of low score. Click to expand.
1
of 1 vote

Should be trivial.
1. Pick one of the trees, call it left tree, and then traverse the right tree, from root.
2. When we traverse a node from the right tree, we insert into the left tree.

Comment hidden because of low score. Click to expand.
1
of 1 vote

a. If you allowed to use extra memory.
1. Convert tree1 and tree2 into sorted arrays by in-order traversal - O(N+M)
2. Merge arrays into one sorted array - O(N+M)
3. Make BST from merged array in a divide-and-conquer manner -O(N+M)
Total - O(M+N)
b. If you must consume a constant memory
Take all elements from first bst and inser into second. It will take O(M log (M+N) ) computaions.

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public class MergeBinarySearchTrees {

private static class Node {

private Node left;
private Node right;

public String toString() {
StringBuilder sb = new StringBuilder();

sb.append("(");

if (left != null) sb.append(left);
if (right != null) sb.append(right);

sb.append(")");

return sb.toString();
}
}

public static void main(String[] args) {

Node n60 = new Node(); n60.payload = 60;
Node n45 = new Node(); n45.payload = 45;

Node n30 = new Node(); n30.payload = 30;
Node n15 = new Node(); n15.payload = 15;
Node n5 = new Node();  n5.payload = 5;

Node n50 = new Node(); n50.payload = 50; n50.left = n45; n50.right = n60;
Node n40 = new Node(); n40.payload = 40; n40.left = n30; n40.right = n50;

Node n10 = new Node(); n10.payload = 10; n10.left = n5; n10.right = n15;

Node n20 = new Node(); n20.payload = 20; n20.left = n10; n20.right = n40;

Node n2 = new Node(); n2.payload = 2;
Node n7 = new Node(); n7.payload = 7;
Node n14 = new Node(); n14.payload = 14;
Node n18 = new Node(); n18.payload = 18;

Node n4 = new Node(); n4.payload = 4; n4.left = n2; n4.right = n7;
Node n16 = new Node(); n16.payload = 16; n16.left = n14; n16.right = n18;

Node n12 = new Node(); n12.payload = 12; n12.left = n4; n12.right = n16;

System.out.println(merge(n20, n12));
}

private static Node merge(Node n1, Node n2) {

while(!todo.isEmpty()) {
Node n = todo.remove(0);
if (n.left != null) {
n.left = null;
}
if (n.right != null) {
n.right = null;
}
inject(n, n2);
}

return n2;
}

private static void inject(Node n, Node n2) {
if (n2.right == null) {
n2.right = n;
return;
}
// otherwise
inject(n, n2.right);
return;
}
// otherwise
if (n2.right.left == null) {
n2.right.left = n;
return;
}
// otherwise
inject(n, n2.right.left);
return;
}
// otherwise
Node temp = n2.right.left;
n2.right.left = n;
n.left = temp;
return;
}

// otherwise
if (n2.left == null) {
n2.left = n;
return;
}
// otherwise
inject(n, n2.left);
return;
}
// otherwise
if (n2.left.right == null) {
n2.left.right = n;
return;
}
// otherwise
inject(n, n2.left.right);
return;
}
// otherwise
Node temp = n2.left.right;
n2.left.right = n;
n.right = temp;
return;
}
}``````

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.