# At one level

Task: to build a list of all the elements of a multilevel list (tree). There is a recursive method:

```(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)))```

List merging in this example will give the complexity of O(n²).
Recursion depth equal to the total number of elements. In these simple tasks is unprofitable to use recursion, because the result is the excessive use of stack memory for the return of function. You can reduce the depth of recursion to a depth of the tree.

```(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))```

Auxiliary function in-one-level2 returns a pair (first . last). Without easy access to the last element of the list algorithm will have difficulty threatening O(n²).
Trees can be looped shape, then you need to control the elements with secondary listings. The complexity of the algorithm will be O(n²). We can say that looped tree is a graph (math.). Nobody stretches graphs at one level.