Find distance between two nodes in binary tree

Question

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;

        public LCAData(TreeNode parent, int count) {
            this.lca = parent;
            this.count = count;

        }
    }

 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);
    }

Answer 1

The algorithm appears to be (without pulling it apart entirely) to exhaustively traverse the entire tree until a node is found where there is one node found on the left and one on the right. And creating an additional set as you go.

The problem here seems to be that your algorithm is very inefficient. That may fit your requirements, if this particular operation is almost never carried out. But normally you could do better.