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.
classSolution {Node lca;int d1Depth;int d2Depth;int lcaDepth;publicbooleanlca(Node node,int d1,int d2,int level) {if (node ==null) {returnfalse; }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 somethingif ((left ==true&& right ==true) || (left ==true&& self ==true) || (self ==true&& right ==true)) {if (lca ==null) { lca = node; lcaDepth = level; } }return self || left || right; }publicintdistance(Node root,int p,int q) {lca(root, p, q,0);return (d1Depth + d2Depth -2* lcaDepth); }}