Implementing equals and hashcode for a BST

Question

This question is sort of a follow up to Implementing hashCode for a BST. My question was poorly thought through and so I got an answer that I am not sure how to use.

I need to implement equals for a BST: so that iff two BSTs are equal in structure and content, then equals returns true. As such, I imagine I also need to implement the hashCode function. I got the answer for the hashCode function such that the trees are equal in structure and content.

@Override
puclic int hashCode(){
  int h = Objects.hashCode(data);//data is int
  int child=0;
  if(null != left)
    child =left.hashCode();
  if(null != right)
    child+= right.hashCode();
  if(0<child) h= h*31+child;
  return h;
}

But then how do I implement the equals function? Will the following work iff the trees are equal in both structure and content?

@Override
public boolean equals(Node otherRoot){
   return root.hashCode() == otherRoot.hashCode();
}

Might there be circumstances where I can false positives?

Or should my hashCode be

@Override
public int hashCode(){
  int h = contents.hashCode();
  h = h * 31 + Objects.hashCode(leftChild);
  h = h * 31 + Objects.hashCode(rightChild);
  return h;
}

and in this latter case, would my equals avoid false positives?

Answer 1

Will the following work iff the trees are equal in both structure and content? root.hashCode() == otherRoot.hashCode()

No, it would not work, because hash code equality is a one-way street: when objects are equal, hash codes must be equal. However, when objects are not equal, hash codes may or may not be equal. This makes sense once you apply a pigeonhole principle: the number of possible hash codes is about 4B, while the number of possible BSTs is virtually infinite.

You can build a comparison in the same way that you built the hash code - i.e. recursively:

• Check if the values at the nodes being compared are equal to each other. If the values are different, return false
• Check if both nodes have a left subtree. If one of them has a left subtree and the other one does not, return false
• Check if both nodes have a right subtree. If one of them has a right subtree and the other one does not, return false
• Apply equals recursively to left subtrees. If the result is false, return false
• Apply equals recursively to right subtrees. If the result is false, return false
• Return true