Python in order traversal to a flat list

Question

I've created a method of a TreeNode class that I'm wanting to return a flat list of an in order tree traversal

My sample tree is:

The in order traversal output should be: [1, 1, 0, 2, 1, 3, 1, 1, 0]

but I'm getting: [2, 1, 1, 0, 1, 3, 1, 1, 0]

Here is my code:

def in_order_list(self, r = []):
    hasLeft = self.left is not None
    hasRight = self.right is not None
    if self is None:
        return
    else:
        if hasLeft:
            self.left.in_order_list(r)
        r.append(self.value)
        if hasRight:
            self.right.in_order_list(r)
    return r

Would anyone be able to give me a clue as to why this is happening?

Thanks Alex

Answer 1

Instead of calling self.left/right.in_order_list(), you're calling self.left/right.pre_order_list().

To accomplish what you want to do a generator function might be better (less memory-consuming and more pythonic) than to accumulate the values in a list:

class Tree(object):
    ...
    def in_order(self):
        if self.left is not None:
            for value in self.left.in_order():
                yield value
        yield self.value  #  <-- yielding the value of the node, not the node itself
        if self.right is not None:
            for value in self.right.in_order():
                yield value

...

tree = Tree(...)

in_order_values = list(tree.in_order())

That way, you don't have to create a list if you only want to iterate over the values:

for value in tree.in_order():
    ...

The algorithm works like this: the generator first descends recursively along the left branch of every node until it hits one with no left sub-node. Then it yields the value of the current node. After that it does the same on the right sub-node, but starting at the current node, not the root node. If we assume there are no cycles in the tree and no infinite branches, then there will definitely be leaf nodes, i.e. nodes with no left or right sub-node. IOW nodes, for which both base cases (self.left/right is None) are reached. Therefore the recursive calls will return, hopefully before we're out of memory or hit the stack limit.

The loop over self.left/right.in_order() is necessary due to the fact that what the call to in_order() returns is a generator, hence the name generator function. The returned generator must be exhausted somehow, e.g. through a loop. In the body of the loop we re-yield the values up one level, where they're re-yielded again, until they reach top level. There we use the values.

If you want to retrieve the nodes themself instead of only their value fields, you could do it like this:

class Tree(object):
    ...
    def in_order(self):
        if self.left is not None:
            for node in self.left.in_order():
                yield node
        yield self  #  <-- yielding the node itself
        if self.right is not None:
            for node in self.right.in_order():
                yield node

You probably want to do this, because not only can you still access the values of the nodes:

for node in tree.in_order():
    do_something_with(node.value)

but also you can do whatever you want with the nodes:

for node in tree.in_order():
    whatever(node.some_other_attribute)

Answer 2

You can write this sort of thing really neatly as a generator, and avoid having to handle lists and appending:

 def in_order(tree):
    if tree is None: return

    for value in in_order(tree.left): yield value
    yield tree.value
    for value in in_order(tree.right): yield value

For example:

>>> class Node(object):
...     def __init__(self, value, left=None, right=None):
...             self.value, self.left, self.right = value, left, right
... 
>>> x = Node(3)
>>> x.left = Node(2)
>>> x.left.left = Node(1)
>>> x.left.left.left = Node(1)
>>> x.left.left.right = Node(0)
>>> x.left.right = Node(1)
>>> x.right = Node(1)
>>> x.right.left = Node(1)
>>> x.right.right = Node(0)
>>> 
>>> in_order(x)
<generator object in_order at 0xb742dbbc>
>>> list(in_order(x))
[1, 1, 0, 2, 1, 3, 1, 1, 0]

Answer 3

It might be a problem with the default argument for r = []

Example:

def foo(list=[]):
    list.append(1)
    print list


foo()
>>> [1]

foo()
>>> [1,1]

Python is keeping the same list over multiple function calls.

Try making the start of your function something like:

def in_order_list(self, r=None):
    if r is None:
        r = []

You might want to post the rest of your code, so we can know what that pre_order function does.

Answer 4

A) firstly as noted by campos.ddc, having the [] be assigned the value to the r parameter is problematic. For details of this consult this answer on Stackoverflow (it is a very common bug)

B) it would seem your "if self is None:" test is redundant, if self was None, you wouldn't be able to call the in_order_list method (assuming this is a method in a class, and not a standalone function)

C) The code could be simplified:

def in_order_list(self, r = None):
    if not r:
        r = []
    if self.left:
        self.left.in_order_list(r)
    r.append(self.value)
    if self.right:
        self.right.in_order_list(r)

D) Questions that are likely "homework" questions, should be labelled as such. >:(