Поиск поддерева в дереве

Задача (из книжки Cracking the coding interview): есть два бинарных дерева (первое поменьше, второе побольше), и надо проверить является ли первое дерево поддеревом второго.

Можно решить её наивным способом. Обходим большее дерево (назовем его T) и для каждого его узла пытаемся сопоставить поддерево с меньшим деревом (назовем его t). Выглядит это примерно следующим образом:

public static <E> boolean isSubtree(final Node<E> tree, 
                                    final Node<E> subtree) {

    return isEquals(tree, subtree) ||
           (tree.left != null && isSubtree(tree.left, subtree)) || 
           (tree.right != null && isSubtree(tree.right, subtree));
}

private static <E> boolean isEquals(final Node<E> tree, 
                                    final Node<E> subtree) {

    if (tree == null && subtree == null)
        return true;
    if (tree == null || subtree == null)
        return false;
    return tree.value == subtree.value &&
            isEquals(tree.left, subtree.left) && 
            isEquals(tree.right, subtree.right);
}

В секции ответов книжки дано именно такое "наивное" решение. В худшем случае каждый шаг сопоставления будет выполняться O(|t|) (за |t| обозначим количество вершин в дереве). И таких шагов будет |T|. В итоге, время работы будет O(|t| * |T|).

Есть ощущение, что можно лучше. Эта задача напомнила мне задачу поиска подстроки в строке. Там наивный алгоритм выглядел примерно также. Но в нашей задаче структура объектов посложнее. При задании дерева в виде связанных ссылками узлов, мы не можем делать по нему произвольные скачки за O(1). Но один из подходов применить можно. Это алгоритм Рабина-Карпа. Вкратце напомню, как он работает. Нам даны исходная строка s, и подстрока p. Считаем хэш функцию образца p (за O(|p|)). Затем для строки s строим просчитываем значениямя хэш-функции всех подстрок строки s длины |p|. Считая хэш-функцию инкрементально, выполняем этот шаг за O(|s|). На каждом шаге сравниваем значение с подсчитанным ранее значением хэш-функции p. При равенстве, есть очень большая вероятность, что мы нашли подстроку. Таким образом при "хорошей" хэш-функции алгоритм работает за O(|s| + |p|).

Также можно поступить и в нашей задаче. Для начала посчитаем значение хеш-функции для каждого поддерева исходного дерева. Получаем отображение из узлов дерева в значение хеш-функции поддерева с корнем в этом узле.
Итак:
1. Рассчитываем значение хеш-функции для каждого поддерева дерева T.
2. Затем рассчитываем хеш-функцию для второго дерева t. В данном случае нам нужно значение только для корня.
3. И наконец обходим дерево T и проверяем равны ли значения хеш-функции для поддерева T и дерева t.

public static <E> boolean isSubtree(final Node<E> tree, 
                                   final Node<E> subtree) {
    
    final Map<Node<E>, Long> nodeToHash = new HashMap<>();
    calculateNodesHashes(tree, nodeToHash);
    final long subtreeHash = 
        calculateNodesHashes(subtree, new HashMap<>());
    return isSubtree(tree, subtree, subtreeHash, nodeToHash);
}

private static <E> boolean isSubtree(final Node<E> tree, 
                               final Node<E> subtree,
                               final long subtreeHash, 
                               final Map<Node<E>, Long> nodeToHash) {
    
    if (tree == null)
        return false;
    if (nodeToHash.get(tree) == subtreeHash) {
        if (checkSubtree(tree, subtree)) {
            return true;
        }
    }
    return isSubtree(tree.left, subtree, subtreeHash, nodeToHash) ||
            isSubtree(tree.right, subtree, subtreeHash, nodeToHash);
}

private static <E> long calculateNodesHashes(final Node<E> n, 
                               final Map<Node<E>, Long> nodeToHash) {

    final long hash = calculateHash(n.value,
        n.left==null ? 0 : calculateNodesHashes(n.left, nodeToHash),
        n.right==null ? 0 : calculateNodesHashes(n.right, nodeToHash)
    );
    nodeToHash.put(n, hash);
    return hash;
}

private static long calculateHash(final Object value, 
                                  final long leftNodeHash, 
                                  final long rightNodeHash) {
    
    return value.hashCode() + 17*(leftNodeHash + 17 * rightNodeHash);
}    

Оценим производительность нашего алгоритма. Рассчитывая значение хэш-функции на основе значений хэш-функций правого и левого поддеревьев получаем асимптотику расчета хеш-функций за размер дерева (O(|t|)). Расчет значений хеш-функции для каждого поддерева дерева T (1) происходит за O(|T|). Расчет значения хеш-функцию для второго дерева t (2) за O(|t|). Ну и на обход дерева (3) занимает O(|T|) (в принципе, если сначала рассчитать (2), то шаги (1) и (3) можно совместить). Итого: O(|T|) + O(|t|) + O(|T|) -> O(|T| + |t|). Расчет был сделан при отсутствии коллизий. Конечно, если хэш-функция будет плохой, то из-за коллизий, производительность алгоритма деградирует до O(|T| * |t|). Но на практике вероятность большого количества коллизий очень низка.