returns the preorder list of a tree in python

I'm new to python and am trying to write a function that will return the preorder list of a tree recursively. I can get it to get the preorder list, however, it comes with a whole lot of unwanted empty lists from the recursive interaction with the base case.

The code is:

def BinPreOrder(T):
    if Is_EmptyBinTree(T):
        return []
    else:
        return BinRoot(T), BinPreOrder(Left(T)), BinPreOrder(Right(T))

How can I get an output of a list of just the values of every node (no empty lists or the like)?

Thanks so much,

Solution

I assume that you want a flat list, not a tuple of tuples as your answer. The first problem is that

BinRoot(T), BinPreOrder(Left(T)), BinPreOrder(Right(T))

is a tuple with three elements, not a list. The recursive calls will also return tuples, so you will end a tuple of tuples.

The second problem is all the occurrences of None in your result. As several people have pointed out already, python functions always return None by default, so you have to explicitly avoid the None's.

Try something like this:

def BinPreOrder(T):
    if not Is_EmptyBinTree(T):
        answer = [BinRoot(T)] 
        left = BinPreOrder(Left(T))
        if left is not None:
           answer.extend(left) 
        right = BinPreOrder(Right(T))
        if right is not None:
           answer.extend(right)
        return answer

EDIT: There's a shorter, clearer way to do this. Instead of letting it return None for empty subtrees, make it return an empty list. Then you can just concatenate the three lists. I was focussing on addressing the problems with your code, instead of thinking about the problem itself. Sorry

def BinPreOrder(T):
    if Is_EmptyBinTree(T): return []
    return [BinRoot(T)] + BinPreOrder(Left(T)) + BinPreOrder(Right(T))