First hash for `t`

is calculated, then it is passed to `hashAndCompare`

which is calculating the hash of `s`

but on each subtree checks whether the current subtree hash is equal to `t`

's hash. Only if we have a hash collision we fully compare both subtrees.

```
boolean hasSub = false;
public boolean isSubtree(TreeNode s, TreeNode t) {
if (s == null) return t == null;
hashAndCompare(s, t, hashAndCompare(t, null, 0));
return hasSub;
}
private int hashAndCompare(TreeNode s, TreeNode t, int tHash) {
if (s == null) return 0;
int myHash = hashAndCompare(s.left, t, tHash) + hashAndCompare(s.right, t, tHash) + (s.val == 0? 1337 : s.val) * 401;
if (myHash == tHash && !hasSub) hasSub = equals(s, t);
return myHash;
}
private boolean equals(TreeNode s, TreeNode t) {
if (s == null || t == null) return s == t;
if (s.val != t.val) return false;
return equals(s.left, t.left) && equals(s.right, t.right);
}
```

Details about hash function:

Hash collisions should occur only once or at most some constant amount of times, depending on the hash function you choose (Integer's `hashCode()`

is very bad here since it's just the number). I just used a random prime and redirected zero to a random number, since we need `0`

hash for `null`

nodes. Would work without this, but leafs with `0`

value would create much more collisions :). It works well, but you could construct a bad testcase for it. A more sophisticated hashCode would prevent this (especially breaking natural order would probably be beneficial for edge cases).