Find distance between two nodes in binary tree

Find distance between two nodes in binary tree

Many answers on the net for 'finding Least Common Ancestor in binary tree'
and its supplementary question 'find distance between 2 nodes' have 4
issues 1) Does not consider duplicates 2) Does not consider if input node
is invalid/absent/not in tree 3) Use extra / aux storage 4) Not truncating
the traversal although answer is obtained. I coded this sample to overcome
all handicaps. but since I did not find 'a single' answer in this
direction, I would appreciate if my code has a significant disadvantage
which I am missing. Maybe there is none. Additional eyeballs appreciated.
public int distance(int n1, int n2) {
LCAData lcaData = new LCAData(null, 0, 0);
int distance = foundDistance (root, lcaData, n1, n2, new
HashSet<Integer>());
if (lcaData.lca != null) {
return distance;
} else {
throw new IllegalArgumentException("The tree does not contain
either one or more of input data. ");
}
}
private static class LCAData {
TreeNode lca;
int count;
int distance;
public LCAData(TreeNode parent, int count, int distance) {
this.lca = parent;
this.count = count;
this.distance = distance;
}
}
private int foundDistance (TreeNode node, LCAData lcaData, int n1, int
n2, Set<Integer> set) {
assert set != null;
if (node == null) {
return 0;
}
// when both were found
if (lcaData.count == 2) {
return 0;
}
// when only one of them is found
if ((node.item == n1 || node.item == n2) && lcaData.count == 1) {
// second element to be found is not a duplicate node of the
tree.
if (!set.contains(node.item)) {
lcaData.count++;
return 1;
}
}
int foundInCurrent = 0;
// when nothing was found (count == 0), or a duplicate tree node
was found (count == 1)
if (node.item == n1 || node.item == n2) {
if (!set.contains(node.item)) {
set.add(node.item);
lcaData.count++;
}
// replace the old found node with new found node, in case of
duplicate. this makes distance the shortest.
foundInCurrent = 1;
}
int foundInLeft = foundDistance(node.left, lcaData, n1, n2, set);
int foundInRight = foundDistance(node.right, lcaData, n1, n2, set);
// second node was child of current, or both nodes were children
of current
if (((foundInLeft > 0 && foundInRight > 0) ||
(foundInCurrent == 1 && foundInRight > 0) ||
(foundInCurrent == 1 && foundInLeft > 0)) &&
lcaData.lca == null) {
// least common ancestor has been obtained
lcaData.lca = node;
return foundInLeft + foundInRight;
}
// first node to match is the current node. none of its children
are part of second node.
if (foundInCurrent == 1) {
return foundInCurrent;
}
// ancestor has been obtained, aka distance has been found. simply
return the distance obtained
if (lcaData.lca != null) {
return foundInLeft + foundInRight;
}
// one of the children of current node was a possible match.
return (foundInLeft + foundInRight) > 0 ? (foundInLeft +
foundInRight) + 1 : (foundInLeft + foundInRight);
}