Телефонное интервью с Facebook 2014.07.21, 2-й вопрос

Телефонное интервью с Facebook 07/21/2014:
Задача 2

2) Hайти наименьшего общего предка (lowest common ancestor) для двух нод дерева. Ссылки на родителей не являются частью ноды дерева. Это "простое" бинарное дерево, т.е. не являющееся бинарным деревом поиска.

Мое решение: получить путь к двум нодам от корня, затем пройти от первого элемента листа до первого отличающегося элемента. Time complexity O(N) где N - количество элементов дерева.

https://gist.github.com/codekrolik/ec86d6fcbf6c223b9dc9

Тесты для всех решений

https://gist.github.com/codekrolik/2c2b9badeb45bb72fc3f

Слабость моего решения в необходимости двух проходов по дереву для формирования путей к нодам.
Книга Cracking the coding interview дает несколько другое решение данной проблемы. Этот подход я планирую реализовать в качестве тренировки позднее (это и будет, собственно, класс LCA2). По time complexity, насколько я понял, радикально не отличается от моего решения (тоже дает O(N)), но оптимальнее по фактическому количеству операций.