Самый эффективный способ проверки двух бинарных деревьев на равенство

Как бы вы реализовали в Java класс узла бинарного дерева и класс бинарного дерева для поддержки наиболее эффективного (с точки зрения времени выполнения) метода проверки на равенство (также необходимо реализовать) :

    boolean equal(Node<T> root1, Node<T> root2) {}

или

    boolean equal(Tree t1, Tree t2) {}

Сначала я создал класс Node следующим образом:

    public class Node<T> {
        private Node<T> left;
        private Node<T> right;
        private T data;

        // standard getters and setters
    }

а затем метод equals, который принимает 2 корневых узла в качестве аргументов и запускает стандартное рекурсивное сравнение:

    public boolean equals(Node<T> root1, Node<T> root2) {
        boolean rootEqual = false;
        boolean lEqual = false;
        boolean rEqual = false;    

        if (root1 != null && root2 != null) {
            rootEqual = root1.getData().equals(root2.getData());

            if (root1.getLeft()!=null && root2.getLeft() != null) {
                // compare the left
                lEqual = equals(root1.getLeft(), root2.getLeft());
            }
            else if (root1.getLeft() == null && root2.getLeft() == null) {
                lEqual = true;
            }
            if (root1.getRight() != null && root2.getRight() != null) {
                // compare the right
                rEqual = equals(root1.getRight(), root2.getRight());
            }
            else if (root1.getRight() == null && root2.getRight() == null) {
                rEqual = true;
            }

            return (rootEqual && lEqual && rEqual);
        }
        return false;
    } 

Моей второй попыткой было реализовать деревья, использующие массивы и индексы для обхода. Тогда сравнение можно было бы сделать с помощью побитовых операций (И) над двумя массивами - прочитать кусок из 2-х массивов и маскировать один другим с помощью логического И. Мне не удалось заставить мой код работать, поэтому я не публикую его здесь (буду признателен за реализацию второй идеи, а также за ваши улучшения).

Есть мысли, как наиболее эффективно выполнить тест на равенство для бинарных деревьев?

EDIT

Вопрос предполагает структурное равенство. (Не семантическое равенство)

Однако код, проверяющий семантическое равенство, например. «Должны ли мы считать два дерева равными, если их содержимое идентично, даже если их структура различна?» Было бы просто перебирать дерево по порядку, и это должно быть просто.