# Easy recursive Java O(n+m) solution beats 99,9% without KMP (using Hash)

• 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);
}
``````

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).