Country: India
Interview Type: Phone Interview

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

just xor the corresponding elements of the 2 trees

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

Level order/pre-order serialization/deserialization with diff. But, there is a problem, for example, when you have 1 2 3 and 4 5 # you will get diff as 3 3 3. Assume, you get 1 2 3 and 3 3 3 and you have to generate 4 5 #, so 3-3=0 means in fact #... this means you have to code 0 somehow or not allowed 0 in your tree. This is how I would do it.

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

I think the idea with serialization is too complicated... I doubt this was what the interviewer wanted. But, the problem is easy... I didn't check all the corner cases, but this should be the solution (like Setu said... is just a xor between nodes, however the problem with id=0 remains):

``````public class Solution {

private class Node {
public Node left;
public Node right;
public int id ;

public Node(int id) {
this.left = null;
this.right = null;
this.id = id;
}
};

private Node generateDiff(Node u, Node v) {
if (u == null && v == null)
return null;

int id = 0;
if (u != null)
id = u.id;
if (v != null)
id ^= v.id;

Node n = new Node(id);
n.left = generateDiff(u == null ? null : u.left, v == null ? null : v.left);
n.right = generateDiff(u == null ? null : u.right, v == null ? null : v.right);
return n;
}

private Node generateBTfromDiff(Node d, Node u) {
if (d == null && u == null)
return null;

int id = d.id;
if (u != null)
id ^= u.id;
if (id == 0)
return null;

Node n = new Node(id);
n.left = generateBTfromDiff(d.left, u == null ? null : u.left);
n.right = generateBTfromDiff(d.right, u == null ? null : u.right);
return n;
}

private Node[] buildBT() {
Node [] roots = new Node[2];
roots[0] = new Node(1);
roots[0].right = new Node(3);
roots[0].left = new Node(9);
roots[0].right.left = new Node(8);

roots[1] = new Node(2);
roots[1].right = new Node(7);
roots[1].left = new Node(4);
roots[1].left.right = new Node(5);
return roots;
}

private boolean checkBT(Node u, Node v) {
if (u == null && v == null)
return true;
else if (u == null || v == null)
return false;

if (u.id != v.id)
return false;

return checkBT(u.left, v.left) && checkBT(u.right, v.right);
}

/* The MAIN ---------------------------------------------------------------------------------*/
public static void main (String args[]) {
BinaryTreeDifference t = new BinaryTreeDifference();
Node roots[] = t.buildBT();
Node d = t.generateDiff(roots[0], roots[1]);
Node root_1 = t.generateBTfromDiff(d, roots[0]);
Node root_0 = t.generateBTfromDiff(d, roots[1]);
System.out.println("root 0 > Same ?  " + t.checkBT(root_0, roots[0]));
System.out.println("root 1 > Same ?  " + t.checkBT(root_1, roots[1]));
}
}``````

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.