1

Hello I am new to programing so at school we are learning recursion and binary trees. But for me recursion is something that really melts my mind away.

so I was trying out a recursive function on a Binary Tree trying to output the preorder format

def preorder(self, preorder_list):
    """ (BinaryTree) -> list
    Return a list of the items in this tree using a *preorder* traversal.
    """

    if self.root is not EmptyValue:
        if self.left and self.right != None:
            preorder_list.append(self.left.preorder(preorder_list))
            preorder_list.append(self.right.preorder(preorder_list))

def helper_preorder(self):
    preorder_list = []
    self.preorder(preorder_list)

    return preorder_list

When I run this code the output I get is:

for example;

[None, None, None, None]

Now I suspect this has to be a problem with my recursive reasoning. So I would like to know what is the problem with my recursive reasoning and how I can better my self in recursion.

Thanks for your time.

Improve this question
6
  • 2
    Because the list you are passing in is empty? Commented Oct 25, 2014 at 19:34
  • 1
    if self.left and self.right != None: is not correct it would be if self.left is not None and self.right is not None: or if self.left and self.right if you wanted to include all falsey values Commented Oct 25, 2014 at 19:34
  • oh but I wanted an empty list so that I can append to it. Commented Oct 25, 2014 at 19:36
  • I don't know Python but I could post the same in Java; it 'adds' to a list. You surely don't need to be checking the left and right for anything; just call it again for both; your first check handles it next time. Commented Oct 25, 2014 at 19:45
  • 1
    @Ali Passing the empty list is fine, but your preorder function never returns a useful value to append to that list. See my answer Commented Oct 25, 2014 at 20:03

1 Answer 1

Reset to default
2

Your problem is that you're never returning anything from preorder, and Python is implicitly returning None. So you append the return value of the function to your list, but that value is None. Your function should look like this (In pseudo code, not valid Python)1:

preorder(node, list):
    if node is Empty:
        return list
    else:
        new_list.append(node.data)
        preorder(node.left, new_list);
        preorder(node.right, new_list);
        return list

Note that I am duplicating the return statement, so you could optimize this, but I set it up this way because it's easiest to understand recursion if you think of it as a base case or a recursive call.

To understand recursion2, think about breaking a hard problem into smaller, easier problems. I'll take a simple example, one of the classic recursion examples: factorial(n).

What is factorial(n)? That's a really hard question to answer, so let's find something simpler.

From math class, we know that n! = n*(n-1)*(n-2)*...*(2)*(1), so let's start there. We can immediately see that n! = n * (n-1)!. That helps; now we can write a starter of our factorial function:

factorial(n):
    return n * factorial(n-1)

But it's not done yet; if we run that, it'll go forever and not stop3. So we need what's called a base case: a stopping point for the recursion, where the problem is now so simple that we know the answer.

Fortunately, we have a natural base case: 1! = 1, which is true by definition. So we add that to our function:

factorial(n):
    if n == 1: return 1
    else return n * factorial(n)

Just to make it clear how that works, let's do a trace for something small, say n=4.

So we call factorial(4). Obviously 4 != 1, so factorial(4) = 4*factorial(3). Now we repeat the process, which is the beautiful thing about recursion: applying the same algorithm to smaller subsets of the original problem, and building up a solution from those parts.

Our trace looks something like this:

factorial(4) = 4*factorial(3)
factorial(4) = 4*3*factorial(2)
factorial(4) = 4*3*2*factorial(1)

Now, we know that factorial(1) is: it's just 1, our base case. So finally we have

factorial(4) = 4*3*2*1
factorial(4) = 24

1 This is only one possible way; there are others, but this is what I came up with on the spot
2 You must first understand recursion (Sorry; I couldn't resist)
3 In the real world, it will eventually stop: because each recursive call uses some memory (To keep track of function parameters and local variables and the like), code that recurses infinitely will eventually exceed the memory allocated to it, and will crash. This is one of the most common causes of a stack overflow error

Improve this answer
Sign up to request clarification or add additional context in comments.

7 Comments

@Ali node.data is how you identify the node. My model is a simple one where each node only contains one thing (A positive integer, say), but in realistic implementations you would store a unique key and some other information (Like a name) in the node
okay when I try that.. it gives me an error: saying builtins.NameError: name 'preorder' is not defined
@Ali What I posted isn't valid Python, it's pseudocode. I'm just showing you what logic you should be following, not exactly what code to write
yes. The code I have written is returning the error. Actually in my program I do not have a .data attribute or any attribute that lets me know the value of the node explicitly... Hence what I am trying to do is actually append directly to the list like this: preorder_list.append(preorder(self.right, preorder_list))
@Ali At some point you need to return something from preorder, otherwise Python will create a list full of he default return value (Which was the point of your question). To append just the node itself, I'd change my code to list.append(node) rather than node.data
|

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.