Creating a List from a Binary Search Tree

Question

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 makeList() that will return a list of all the items in my tree. All the functions in my programs work except the makeList() function and are included to make sure everyone understands the basic structure of how I set up my tree.

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 < current.data:
                    current = current.lChild
                else:
                    current = current.rChild

            if item < 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)

Looking at my makeList() function I can see why it doesn't work but I don't know how to make it work.

EDIT

Ok, I got it! And I even got two answers which are:

def makeList(self, aNode, a = []):
    if aNode != None:
        self.makeList(aNode.lChild, a)
        a += [aNode.data]
        self.makeList(aNode.rChild, a)
    return a

and

def makeList2(self, aNode):
    if aNode is None:
        return []
    return self.makeList2(aNode.lChild) + [aNode.data] + self.makeList2(aNode.rChild)

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?

Another question, so say I call my makeList() function. When Python goes through makeList(), when it gets to the self.makeList(aNode.lChild, a) does it begin running the function again while it's still finishing up the makeList() function or does everything stop and it just starts over with it's new aNode?

I hope that makes sense.

Answer 1

You're so close! makeList can be pretty simple:

def makeList(self, aNode):
    if aNode is None:
        # Stop recursing here
        return []
    return self.makeList(aNode.lChild) + [aNode.data] + self.makeList(aNode.rChild)

Basically, make sure you're not trying to recurse past empty nodes. Then return the list of the left tree, the current node, and the list of the right tree.