Creating a list from a binary search tree

Question

I am trying to list all items in a binary search tree. I understand recursion, but I don’t know how to get it to return each value, and then add it to the list. I want to create a function called makeList() that will return a list of all the elements in my tree. All functions in my programs work, except for 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 understand why it does not work, but I do not know how to make it work.

EDIT

OK I understood! And I even have two answers:

 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 see that I'm not very good at recursion, so it's time to hit books! Does anyone have any good recursion resources?

Another question, so to speak, I call the makeList() function. When Python goes through makeList() , when it gets to self.makeList(aNode.lChild, a) , it starts the function again while it still finishes the makeList() function or everything stops and it just starts with it new aNode ?

Hope this makes sense.

Answer 1

You are so close! makeList can be quite 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 are not trying to restart past empty nodes. Then return the list of the left tree, the current node and the list of the correct tree.

Answer 2

inOrder prints things, but returns nothing, so it is useless to create a list. You need a way to return each node in order. It might be something your class hasn't covered yet, but check the yield command.

Answer 3

The basic idea is as follows:

 def makeList(self): return self.lChild.makeList() + [self.data] + self.rChild.makeList() 

See how this is essentially the same as inOrder?

You have another structure in your program that complicates its implementation, but the basic idea is the same.