Implementing hashCode for a BST

Question

In Java to compare two objections for equality, you must implement both the equals method and the hashCode method. I need to compare two BSTs for equality. How do I implement the hashCode method in such a case? Now, implementing the hashCode on the Node class is simple enough: imagine my data is int. But I cannot just add the values of the node to check if the trees are equal. So how do I do it? Has anyone done this successfully?

I am thinking of many different things that I can do, but I am not sure how scalable they would be. For example I could use level order and for each level multiply by a large prime number, but I can't be sure that this would work. So maybe someone who understands better can help me. Thanks.

Answer 1

I cannot just add the values of the node to check if the trees are equal.

Sure you can. hashCodes do not have to be unique, and if two BSTs have the same contents, then summing the node contents will give you the same results in each case, which satisfies the hashCode contract. Remember -- return 0 is always a valid implementation of hashCode(); uniqueness is not required.

(Summing the hashCodes of the node contents is, in fact, how TreeSet.hashCode() is implemented.)

On the other hand, if you care about structure, you could do something simple like implementing Node.hashCode() with

int h = contents.hashCode();
h = h * 31 + Objects.hashCode(leftChild);
h = h * 31 + Objects.hashCode(rightChild);
return h;

...and that'd get you a decent structure-respecting hash function, too.