How to correctly implement equals(), hashCode() for Tree in Java?

Question

I have a tree structure and I need to override the methods equals/hashCode because I use the check of the expected result in the unit tests.

The problem with tree type structures is that they refer to each other recursively. In particular, parents for children and vice versa.

and if all fields are used in the methods equals/hashCode, then there will be a looping. The question is how to correctly override then in order not to violate the contract.

I will give an example of how I implemented it.

public class App {
    public static void main(String[] args) {
        Book book1 = new Book(1L, "The catcher in the rye");
        Book book2 = new Book(2L, "Rich Dad Poor Dad");

        BookTree bookTree1 = new BookTree(book1);
        BookTree bookTreeChild1 = new BookTree(book2);
        bookTree1.addChild(bookTreeChild1);

        BookTree bookTree2 = new BookTree(book1);
        BookTree bookTreeChild2 = new BookTree(book2);
        bookTree2.addChild(bookTreeChild2);

        if (!bookTree1.equals(bookTree2)) {
            throw new RuntimeException("Invalid override equals");
        }
    }
}

class Book {
    private Long id;
    private String name;

    public Book(Long id, String name) {
        this.id = id;
        this.name = name;
    }

    public Long getId() {
        return id;
    }

    public void setId(Long id) {
        this.id = id;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    @Override
    public boolean equals(Object object) {
        if (this == object) return true;
        if (object == null || getClass() != object.getClass()) return false;
        Book book = (Book) object;
        return Objects.equals(id, book.id) &&
                Objects.equals(name, book.name);
    }

    @Override
    public int hashCode() {
        return Objects.hash(id, name);
    }
}

class Tree<T> {
    private List<Tree<T>> children = new ArrayList<>();
    private Tree<T> parent = null;
    private T data;

    public Tree(T data) {
        this.data = data;
    }

    public Tree(T data, Tree<T> parent) {
        this.data = data;
        parent.addChild(this);
    }

    public List<Tree<T>> getChildren() {
        return children;
    }

    public void addChild(Tree<T> child) {
        child.setParent(this);
        this.children.add(child);
    }

    public void addChild(T data) {
        Tree<T> newChild = new Tree<>(data);
        this.addChild(newChild);
    }

    public void removeChildren() {
        this.children = new ArrayList<>();
    }

    public void addChildren(List<Tree<T>> children) {
        for(Tree<T> t : children) {
            t.setParent(this);
        }
        this.children.addAll(children);
    }

    private void setParent(Tree<T> parent) {
        this.parent = parent;
    }

    public Tree<T> getParent() {
        return parent;
    }

    public T getData() {
        return this.data;
    }

    public void setData(T data) {
        this.data = data;
    }

    public boolean isRoot() {
        return (this.parent == null);
    }

    public boolean isLeaf() {
        return this.children.size() == 0;
    }

    public void removeParent() {
        this.parent = null;
    }

    @Override
    public boolean equals(Object object) {
        if (this == object) return true;
        if (object == null || getClass() != object.getClass()) return false;
        Tree<?> tree = (Tree<?>) object;
        return Objects.equals(children, tree.children) &&
                Objects.equals(data, tree.data);
    }

    @Override
    public int hashCode() {
        return Objects.hash(children, data);
    }
}

class BookTree extends Tree<Book> {

    public BookTree(Book data) {
        super(data);
    }

    public BookTree(Book data, Tree<Book> parent) {
        super(data, parent);
    }
}

As you can see from my implementation, I use only two fields: "data" and "children". Accordingly, my question is whether I implemented the methods equals/hashCode correctly? If wrong, then please show how.

Answer 1

I think @GhostCat's answer where they ask "what is correct?" is crucial. I would like to focus on this part.

The sample given in the OP can be considered correct.

I would name the Tree class TreeNode, however. I think that's a more appropriate name. Then the question becomes are two TreeNodes equal if they have the same data and same children but a different parent? That's the current implementation of the OP. This can be considered correct. If, however, the requirement is that a TreeNode also has the same parent, then the entire tree must be equal when comparing two tree nodes. In that case, it doesn't really make sense to ever compare two tree nodes, why not just compare the two trees from the root node? I say this, because there is value in comparing two nodes within the tree and ask the question, "Are these two subtrees equal, regardless of the different parent?" So I believe the OP's code offers more flexibility than requiring that the parent also be equal. In this case the parent property is used for convenient navigation and not for identity. You can also imagine a TreeNode where there is no parent property and only the parent knows of its children. This would make data integrity easier to maintain (because the link is only stored in the parent), but navigation more challenging).

I favor the approach of thinking of parent as used for navigation or simply removing the parent property from TreeNode (or Tree as the OP calls the class).