Recursive compare two binary search trees

Question

I need to compare two binary search trees and see if they are equal or not. I developed following code that uses recursion.

private boolean compareTrees(BinaryTreeNode n1, BinaryTreeNode n2)
{
    if(n1.getNodeData() != n2.getNodeData())
        return false;
    else
    {
        if(n1.left != null && n2.left != null)
            compareTrees(n1.left, n2.left);

        if(n1.right != null && n2.right != null)
            compareTrees(n1.right, n2.right);   
    }

    return true;
}

The problem is that if two nodes are not equal, the method will return false but because I use recursion, the return value will be overridden to true no matter what. I have been stuck with this problem for all day and nothing worked for me. I searched online but I didn't find anything relevant to my code. Is there any way to break from all nested methods and return value to the first method?

Answer 1

You need to return the result of the subtree comparison:

boolean b1, b2;

if(n1.left != null && n2.left != null)
    b1 = compareTrees(n1.left, n2.left);

if(n1.right != null && n2.right != null)
    b2 = compareTrees(n1.right, n2.right);

return b1 && b2;

But why not just deal with nulls before-hand?

private boolean compareTrees(BinaryTreeNode n1, BinaryTreeNode n2)
{
    if (n1 == null || n2 == null)
        return n1 == n2;  // i.e. both null

    if (n1.getNodeData() != n2.getNodeData())
        return false;

    return compareTrees(n1.left, n2.left) && compareTrees(n1.right, n2.right);
}

Answer 2

I would do it changing the order:

private boolean compareTrees(BinaryTreeNode n1, BinaryTreeNode n2)
{
    boolean equalLeft = false;
    boolean equalRight = false;

    if(n1.getNodeData() == n2.getNodeData())
    {
        if(n1.left != null && n2.left != null){
            equalLeft = compareTrees(n1.left, n2.left);
        } else{
            equalLeft = true;
        }

        if(n1.right != null && n2.right != null){
            equalRight = compareTrees(n1.right, n2.right);
        } else{
            equalRight = true;
        }

        return equalLeft && equalRight;

    } else{

         return false;
    }
}

Answer 3

Try to face the problem avoiding null values and using equals() method instead of == comparison for your nodes. I shoud do it this way:

private boolean compareTrees(BinaryTreeNode n1, BinaryTreeNode n2){

//avoid nulls :TDD
if (n1==null && n1==n2) 
    return true;
if ((n1==null && n2!=null) || (n2==null && n1!=null)) 
    return false;

//ensure logic without nulls, comparing with equals() method
boolean areEquals =  n1.getNodeData().equals(n2.getNodeData());

//compare left
areEquals = areEquals && compareTrees(n1.left, n2.left);
//if still equals, compare right
if(areEquals) areEquals = areEquals && compareTrees(n1.right, n2.right);  

return areEquals;

}

Answer 4

Effectively, your code could reduce to:

private boolean compareTrees(BinaryTreeNode n1, BinaryTreeNode n2)
{
       if(n1==null || n2==null) return n1==n2;
       return (n1.getNodeData()==n2.getNodeDate()) && compareTrees(n1.left, n2.left) && compareTrees(n1.right, n2.right) 
}

I will tell you couple of problems your code has.

1. Termination criteria when root is null (it will always happen in the end).

2. Return statements in recursive calls. You are always returning the true in the end.

PS: If you add NULL checks (explained in 1), you need not to add null checks in the subsequent recursive calls. Now the second half of your code will look like:

return compareTrees(n1.left, n2.left) && compareTrees(n1.right, n2.right);