title: Creating a List from a Binary Search Tree
body: <p>I'm trying to make a list of all items in a binary search tree. I understand the recursion but I don't know how to make it return each value and then append it into a list. I want to create a function called <code>makeList()</code> that will return a list of all the items in my tree. All the functions in my programs work except the <code>makeList()</code> function and are included to make sure everyone understands the basic structure of how I set up my tree.</p>
  
  <pre><code>class Node(object):
      def __init__(self, data):
          self.data = data
          self.lChild = None
          self.rChild = None
  
  class Tree(object):
      def __init__(self):
          self.root = None
  
      def __str__(self):
          current = self.root
  
      def isEmpty(self):
          if self.root == None:
              return True
          else:
              return False
  
      def insert (self, item):
          newNode = Node (item)
          current = self.root
          parent = self.root
  
          if self.root == None:
              self.root = newNode
          else:
              while current != None:
                  parent = current
                  if item &lt; current.data:
                      current = current.lChild
                  else:
                      current = current.rChild
  
              if item &lt; parent.data:
                  parent.lChild = newNode
              else:
                  parent.rChild = newNode
  
      def inOrder(self, aNode):
          if aNode == None:
              pass
          if aNode != None:
              self.inOrder(aNode.lChild)
              print aNode.data
              self.inOrder(aNode.rChild)
  
      def makeList(self, aNode):
          a = []
          self.inOrder(aNode)
          a += [aNode.data]
          print a
  
  n = Tree()
  for i in [4,7,2,9,1]:
      n.insert(i)
  
  n.makeList(n.root)
  </code></pre>
  
  <p>Looking at my <code>makeList()</code> function I can see why it doesn't work but I don't know how to make it work.</p>
  
  <p><strong>EDIT</strong></p>
  
  <p>Ok, I got it! And I even got two answers which are:</p>
  
  <pre><code>def makeList(self, aNode, a = []):
      if aNode != None:
          self.makeList(aNode.lChild, a)
          a += [aNode.data]
          self.makeList(aNode.rChild, a)
      return a
  </code></pre>
  
  <p>and</p>
  
  <pre><code>def makeList2(self, aNode):
      if aNode is None:
          return []
      return self.makeList2(aNode.lChild) + [aNode.data] + self.makeList2(aNode.rChild)
  </code></pre>
  
  <p>And looking back I can see that I do not understand recursion very well so it's time to hit the books! Anyone have any good resources on recursion?</p>
  
  <p>Another question, so say I call my <code>makeList()</code> function. When Python goes through <code>makeList()</code>, when it gets to the <code>self.makeList(aNode.lChild, a)</code> does it begin running the function again while it's still finishing up the <code>makeList()</code> function or does everything stop and it just starts over with it's new <code>aNode</code>?</p>
  
  <p>I hope that makes sense.</p>