Почему в этом обходе дерева выполняются только log (N) рекурсивные вызовы?

Question

Следующий код является решением этой проблемы: «Учитывая двоичное дерево, разработайте алгоритм, который создает связанный список всех узлов на каждой глубине (например, если у вас есть дерево с глубиной D, вы получитеD связанный список ".

void createLevelLinkedList(TreeNode root, ArrayList<LinkedList<TreeNode>>lists, int level) {

   if(root == null) return; //base case

   LinkedList<TreeNode> list = null;
   if (lists.size()==level){ //Level not contained in list
      list = new LinkedList<TreeNode>();
      lists.add(list);
   } else{
     list = lists.get(level);
   }

   list.add(root);
   createLevelLinkedlist(root.left, lists, level+1);
   createLevelLinkedList(root.right, lists, level+1);
}

ArrayList<LinkedList<TreeNode>> createLevelLinkedList(TreeNode root){

   ArrayList<LinkedList<TreeNode>> lists = new ArrayList<LinkedList<TreeNode>>();

   createLevelLinkedlist(root, lists, 0);
   return lists;

}

Согласно решению, этот код имеет время выполнения O (N), но использует рекурсивные вызовы O (log N). Почему существует только рекурсивный O (log N)вызовы? Похоже, что в каждом вызове всегда есть два новых рекурсивных вызова, сделанных для root.left и root.right, поэтому не должно быть O (N) рекурсивных вызовов? Один для каждого узла в дереве?

"Решение использует O (log N) рекурсивных вызовов (в сбалансированном дереве), каждый из которых добавляет новый уровень в стек"

Извините, я действительно смущен, буду благодарен за объяснение, спасибо!