title: Turning a tree into a list - Iteration versus Recursion
body: <p>This was a question in a cs exam I wrote a few months ago and scored zero points in.
  We have a binary tree structure built as follows:</p>
  <pre><code>class Tree:
      def __init__(self,left=None, value=None, right=None):
          if value == None or left == None or right == None:
              self.empty = True
          else:
              self.empty = False
              self.value = value
              self.left = left
              self.right = right
  </code></pre>
  <p>Then a function for extracting the values from the tree and pouring them into a list was given:</p>
  <pre><code>def to_list(self):
          if self.empty:
              return []
          else:
              ll = self.left.to_list()
              lr = self.right.to_list()
              return ll + [self.value] + lr
  </code></pre>
  <p>Importantly - This function retains the order of elements as it was represented in the tree.</p>
  <p>The task then was to write an iterative version of this &quot;to_list&quot; function that also retains this structure.</p>
  <p>I have since written a functioning version but it is painfully bad so I'd like the input of more knowledgeable programmers.</p>
  <p>Here is my version:</p>
  <pre><code>def to_list_iter(self):
          stack = []
          if self.empty:
              return []
          else:
              stack.append(self)
              while True:
                  for x in range(len(stack)):
                      if type(stack[x]) != int:
                          middle = stack[x]
                          if middle.empty == False:
                              stack[x] = middle.value
                              stack.insert(x,middle.left)
                              stack.insert(x+2,middle.right)
                          else:
                              stack[x] = 0
                                  
                  check = True
                  for z in stack:
                      if type(z) != int:
                          check = False
                  if check == True:
                      return list(filter(lambda a: a != 0, stack))
  </code></pre>