[ How do you recurse through two return statements? [JAVA] ]

I am currently trying to implement a binary search tree shape comparison and am having trouble with one line of my code.

    if(treeStructOne.getHeight() == 1 && treeStructTwo.getHeight() == 1) //Base Case, if both are empty then they must be equal!
    {
        return true;
    }
    if(treeStructOne.getHeight()  != treeStructTwo.getHeight()) //First make sure height is the same, if not, must be unequal
    {
        return false;
    }
        if(treeStructOne.hasLeft()  && treeStructTwo.hasLeft())
        {
            return similar(treeStructOne.getLeft(),treeStructTwo.getLeft());

        }
        if(treeStructOne.hasRight() && treeStructTwo.hasRight()) //PROBLEM IS HERE
        {
            return similar(treeStructOne.getRight(),treeStructTwo.getRight());  
        }        
        return false;

The problem occurs when a node on Tree 1 and 2 has a left child, but only tree 1 has a right and not Tree 2. After it checks that they both have left children, it does not run the the check on right children if left is true. Is this to do with the way recursion works in java?

Answer 1

if both trees hasLeft() returns true then your method will return in that if clause. My guess is you want to assign the result from the similar call in the last two if clauses and after the if clause do something like

return leftSimilar && rightSimilar;

Answer 2

The first two if's will work, but the last part should capture the conditions of p implies q which is ~p or q for both left and right. In other words, if treeStructOne has a left subtree and treeStructTwo has a left subtree, then check to see if they are similar (return similar...)

if(treeStructOne.getHeight() == 1 && treeStructTwo.getHeight() == 1) //Base Case, if both are empty then they must be equal!
    {
        return true;
    }
if(treeStructOne.getHeight()  != treeStructTwo.getHeight()) //First make sure height is the same, if not, must be unequal
    {
        return false;
    }
return (treeStructOne.hasLeft() && treeStructTwo.hasLeft()
         ? similar(treeStructOne.getLeft(),treeStructTwo.getRight())
         : false)
    && (treeStructOne.hasRight() && treeStructTwo.hasRight()
         ? similar(treeStructOne.getRight(),treeStructTwo.getRight())
         : false);

Answer 3

The return statement immediately returns from the current method, i.e. the remainder of the method will not be executed.

In your case, you want to make two recursive calls before returning from the method. You can do this with:

boolean similarLeft;
if(treeStructOne.hasLeft()  && treeStructTwo.hasLeft()) {
    similarLeft = similar(treeStructOne.getLeft(),treeStructTwo.getLeft());
} else {
    similarLeft = ?; // TODO what is good condition here?
}

then do the same for the right side and conclude with

return similarLeft && similarRight;

However, for truly ideomatic java, I'd do the null checks after invoking the method rather then before it, thereby reducing code duplication:

boolean similar(TreeStruct x, TreeStruct y) {
    if (x == null) {
        return y == null;
    } else {
        return y != null && similar(x.left, y.left) && similar(x.right, y.right);
    }
}