Find the distance between two keys in a binary tree, no parent pointers are given. Distance between two nodes is the minimum number of edges to be traversed to reach one node from other.
class Solution {
Node lca;
int d1Depth;
int d2Depth;
int lcaDepth;
public boolean lca(Node node, int d1, int d2, int level) {
if (node == null) {
return false;
}
boolean self = false;
if (node.data == d1) {
d1Depth = level;
self = true;
}
if (node.data == d2) {
d2Depth = level;
self = true;
}
boolean left = lca(node.left, d1, d2, level + 1);
boolean right = lca(node.right, d1, d2, level + 1);
// moment of reckoning
// both child found something
// one child or self found something
if ((left == true && right == true) || (left == true && self == true) || (self == true && right == true)) {
if (lca == null) {
lca = node;
lcaDepth = level;
}
}
return self || left || right;
}
public int distance(Node root, int p, int q) {
lca(root, p, q, 0);
return (d1Depth + d2Depth - 2 * lcaDepth);
}
}