В один уровень

  Задача: выстроить в один список все элементы из многоуровневого списка (дерева). Есть рекурсивный способ:

(nil  defmethod in-one-level  ()
  (nil  if  (nil  = this)
    nil
    (nil  cons  this  nil)))
('cons  defmethod in-one-level  ()
  (((this first)  in-one-level) + ((this  rest) in-one-level)))

  Слияние списка в данном примере даст сложность O(n²).
  Глубина рекурсии равна полному количеству элементов. В таких простых задачах невыгодно использовать рекурсию, так как результатом будет чрезмерное использование памяти стека для возврата из функций. Можно уменьшить глубину рекурсии до глубины данного дерева.

(nil  defmethod in-one-level2 ()
  (nil  if  (nil  consp this)
    (nil  let ((i this) first last)
      (nil  do-while
        (nil  let ((resulti ((i first)  in-one-level2)))
          (nil  let ((firsti  (resulti  first)) (lasti  (resulti  rest)))
            (nil  if  (nil  consp firsti)
              (nil  if  (nil  consp last)
                (nil  progn
                  (last setrest firsti)
                  (nil  setq  last  lasti))
                (nil  setq  first firsti  last  lasti))
              (nil  let ((last2 (nil  cons  firsti  nil)))
                (nil  if  (nil  consp last)
                  (nil  progn
                    (last setrest last2)
                    (nil  setq  last  last2))
                  (nil  setq  first last2 last  last2))))))
        (nil  setq  i (i  rest))
        (nil  consp i))
      (nil  cons  first last))
    (nil  cons  this  this)))
(nil  defmethod in-one-level  ()  ((this  in-one-level2)  first))

  Функция вспомогательная in-one-level2 возвращает пару (first . last). Без быстрого доступа к последнему элементу списка алгоритм будет иметь угрожающую сложность O(n²).
  Деревья могут иметь зацикленную форму, тогда нужно будет контролировать элементы с помощью вспомогательных списков. Сложность алгоритма станет O(n²). Можно сказать, что зацикленное дерево это граф (мат.). Графы никто не растягивает в один уровень.