CODEWITHSUNDEEP
javaalgorithmrecursiontree
John Mòf
John Mòf

Reputation: 115

Test if two binary trees are equal

I know this may be a duplicate post, but I would submit my own code to your attention. I wrote the following recursive procedure, but I would like to optimize it. I would like to stop the treeCompare method as soon as I find a node different from other, instead of comparing all nodes.

Thanks in advance for your help.

This is my thin Node class:

public class Node {
    public Node father;
    public Node left;
    public Node right;
}

And this is my comparator method:

private boolean treeCompare(Node firstNode, Node secondNode) {
    if (firstNode == null && secondNode == null)
        return true;
    else if (firstNode == null || secondNode == null)
        return false;

    boolean isLEquals = treeCompare(firstNode.left, secondNode.left);
    boolean isREquals = treeCompare(firstNode.right, secondNode.right);

    return firstNode.equals(secondNode) && isLEquals && isREquals;
}

Upvotes: 1

Views: 2227

Answers (1)

andrucz
andrucz

Reputation: 2021

private boolean treeCompare(Node firstNode, Node secondNode) {
    if (firstNode == secondNode)
        return true;

    if (firstNode == null || !firstNode.equals(secondNode))
        return false;

    return treeCompare(firstNode.left, secondNode.left) && treeCompare(firstNode.right, secondNode.right);
}

Upvotes: 5

Related Questions