Google Interview Question
Country: India
Interview Type: Phone Interview
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.
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]));
}
}
just xor the corresponding elements of the 2 trees
- Setu March 22, 2019