Java – implement equals and hashcode for BST

This problem is a follow-up problem of implementing hashcode for a BST My question was hard to think of, so I got an answer I wasn't sure how to use

I need to implement equals for BST: in this way, if two BSTS are equal in structure and content, equals returns true Therefore, I think I also need to implement the hashcode function I got the answer to the hashcode function, making the structure and content of the tree the same

@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 how do I implement the equals function? If the trees are the same in structure and content, will the following work work?

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

Is there any possibility of false positives?

Or my hashcode should be

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

In the latter case, will my equality avoid false positives?

Solution

No, it doesn't work because hash code equality is one-way: when objects are equal, hash codes must be equal However, when the objects are not equal, the hash codes may be the same or not equal Once you apply the pigeonhole principle, it makes sense: the number of possible hash codes is about 4b, while the number of possible BSTS is actually unlimited

You can build comparisons the same way you build hash codes – that is, recursively:

>Check whether the values of the compared nodes are equal If the values are different, return false > to check whether both nodes have left subtree If one of them has a left subtree and the other does not, return false > to check whether both nodes have the correct subtree If one has the correct subtree and the other does not, return false > recursive application is equal to the left subtree If the result is false, return false > recursive application is equal to the right subtree If the result is false, return false > return to true