Изучите GROUP BY, который в случае с MySQL всё аккуратно отсортирует, сгруппирует, а за компанию и посчитает сумму.
Не понимаю, откуда взялся и как работает getTreeSum(), мне кажется какой-то лишний оверкилл может происходить внутри.
Дальше - допишите EXPLAIN перед своим запросом и покажите результат - это скажет, в каких местах всё плохо.
Подозреваю, запрос должен делиться на 2 части - вывод идшников дочерних узлов вложенным подзапросом и SUMмма по полученному:
WHERE id IN (select .... left_key >= левый_ключ_необходимого_узла AND right_key <= правый_ключ_необходимого_узла)