Как создать дерево AVL из списка значений ArrayList за время O (n)?

Мое задание - создать дерево AVL из отсортированного списка значений массива за время O (n), где n это количество значений

Я работал над этим, но я не могу получить время O (n), лучшее, что я могу получить, это O (nlog (n))

Моя проблема в том, что каждый раз, когда узел вызывает вставляется несбалансированное дерево, Мне нужно сделать еще один цикл, чтобы найти несбалансированный узел и применить вращение (я), чтобы снова сбалансировать дерево.

Любая помощь приветствуется, спасибо!