ты говоришь неоднократно "двигаться вверх", но структура дерева не имеет линка parent, а только left/right
Дерево - всего лишь исходные данные, к которым никто не мешает прилепить что-то дополнительное. Кстати, отсутствие линка на родителя - обычай, но не догма.
Нет необходимости строить все возможные пути, а потом отбрасывать лишние. Достаточно знать высоты всех поддеревьев и "корень", через который проходит длиннейший путь.
