Java Binary Trees: Finding the node that reaches two nodes with shortest distance

Question

I'm currently writing a method that searches a binary tree in Java for the node that reaches two nodes in the shortest distance. My idea is that if both nodes exist in the tree, the root would be the first node that can reach both. So I recurse and check the left/right of the root to see if they too can reach both. By finding the first node that cannot reach both after finding at least one node that did, I should have the node of shortest distance from the two I'm searching for.

I have broken this task down to two methods, one named canReach that searches the tree for a node and another that uses canReach's boolean return to determine moving down the tree and in what direction, named reachesBoth.

Through debugging I'm pretty confident canReach is accurately searching the tree. However it seems that I'm never coming out of reachesBoth with any answer except null if both the nodes do not exist in the tree or the root if they are, never anything in between.

Is repeatedly checking for access to both nodes while navigating down the tree a good idea? If anyone can see where my method reachesBoth is bugged, I would appreciate the insight.

public boolean canReach(T d) {
        // Helper method for reachesBoth. Takes an argument of data of a Node
        int comp = d.compareTo(data); // Compare data to current node
        if (comp == 0) return true; // Found the node
        if (comp < 0) { // search left for the node
            if (left != null) {
                if (left.canReach(d) == true) return true;
            }
            return false;
        }
        if (comp > 0) { // search right for the node
            if (right != null) {
                if (right.canReach(d) == true) return true;
            }
            return false;
        }
        return false; // Cannot find the node in our tree
    }

    public T reachesBoth(T a, T b) {
        if (canReach(a) == true && canReach(b) == true) { 
            // Found the first node that can reach both desired nodes.
            // Must continue to see if a node with shorter distance
            // can reach both nodes as well.
            if (left != null && right != null) {
                // Case 1: Two more branches to check 
                if (left.reachesBoth(a, b) != null) left.reachesBoth(a, b);
                if (right.reachesBoth(a, b) != null) right.reachesBoth(a, b);
                //Both branches cannot reach both nodes sooner than we can.
                if (left.reachesBoth(a, b) == null & right.reachesBoth(a, b) == null) {
                    return this.data;
                } 
            }
            if (left != null && right == null) {
                // Case 2: Only left branch to check
                if (left.reachesBoth(a, b) == null) return this.data;
            }
            if (left == null && right != null) {
                // Case 3: Only right branch to check
                if (right.reachesBoth(a, b) == null) return this.data;
            }
            // Case 4: No more tree to search for a better solution
            if (left == null && right == null) return this.data;

        }

        return null; // Cannot locate both nodes in our tree from our start
    }

Answer 1

Change your recursion to return when it checks the left and right children:

if (left.reachesBoth(a, b) != null) return left.reachesBoth(a, b);

if (right.reachesBoth(a, b) != null) return right.reachesBoth(a, b);