Удаление повторяющихся поддеревьев из двоичного дерева

Я должен разработать алгоритм в рамках дополнительной домашней работы. Этот алгоритм должен сжимать двоичное дерево, преобразовывая его в DAG, удаляя повторяющиеся поддеревья и перенаправляя все эти соединения на одно левое исходное поддерево. Например, у меня есть дерево (я даю предварительный порядок узлов):

1 2 1 3 2 1 3

Алгоритм должен удалить правильное соединение (правое поддерево, что означает 2 1 3) из 1 ( root) и перенаправить его на левое соединение (потому что эти поддеревья одинаковы и left было первым в предварительном порядке, поэтому мы оставляем только левое)

Как я это вижу: я передаю предварительный порядок дерева. Для текущего узла 'w' я запускаю рекурсию, которая должна определить (если существует) исходное поддерево, равное поддереву с корнем 'w'. Я сокращаю рекурсию, если нахожу равное поддерево (и делаю то, что должно быть сделано) или когда добираюсь до 'w' в поиске той же рекурсии поддеревьев. Конечно, я предсказываю некоторые небольшие улучшения, такие как сравнение только поддеревьев с равным количеством узлов.

Если я не ошибаюсь, это дает сложность O (n ^ 2), где n - количество узлов данного двоичного дерева. Есть ли шанс сделать это быстрее (я думаю, что есть). Возможен ли линейный алгоритм?

Жалко, что у моего алгоритма наконец-то сложность O (n ^ 3). Ваши ответы с хешированием, наверное, мне очень пригодятся через какое-то время, когда я узнаю гораздо больше .. Пока что для меня это слишком сложно ..

Последний вопрос. Есть ли шанс сделать это за O (n ^ 2) с использованием элементарных методов (без хеширования)?