# Returning a list of the values from the binary tree

I want to return a list of the values from the binary tree. Is there a shorter and more efficient way to write the method for numbers?

class BTNode(object):
"""A node in a binary tree."""

def __init__(self, item, left=None, right=None):
"""(BTNode, object, BTNode, BTNode) -> NoneType
Initialize this node to store item and have children left and right,
as well as depth 0.
"""
self.item = item
self.left = left
self.right = right
self.depth = 0  # the depth of this node in a tree

def number(self: 'BTNode') -> list:
lst = []

if self.right is None and self.left is None:
lst.append(self.item)
else:
lst.append(self.item)
if self.left:
left = self.left.number()
lst.extend(left)
if self.right:
right = self.right.number()
lst.extend(right)
return lst

• I think number would be better named enumerate. Dec 28 '13 at 18:56

1. There is no docstring for the number method.

2. There are no test cases. This kind of code would be an ideal opportunity to write some doctests.

3. The depth property is always 0. This seems useless.

4. The method name number is misleading. (It does not return a number.) I would call it something like flattened_pre_order because it flattens the tree into a list using pre-order traversal.

5. The variable name lst is misspelt. Better to call it something like result.

6. This code:

if self.right is None and self.left is None:
lst.append(self.item)
else:
lst.append(self.item)


can be replaced with:

lst.append(self.item)


since it doesn't matter whether the condition is true or false.

7. There's quite a lot of copying going on in the traversal of the tree: each time you call a.extend(b), Python has to copy out the list b. This copying causes the traversal of a tree with n nodes to take O(n2) time instead of O(n). See below for a way to avoid this copying.

8. You use recursion to visit the child nodes, which means that traversing a very deep tree will exceed Python's maximum recursion depth:

>>> n = None
>>> for i in range(1000): n = BTNode(i, n)
...
>>> n.number()
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
File "cr33662.py", line 22, in number
left = self.left.number()
[... many lines omitted ...]
RuntimeError: maximum recursion depth exceeded


The way to avoid this is to maintain your own stack, like this:

def flattened_pre_order(self: 'BTNode') -> list:
"""Return a list of items in the tree rooted at this node, using
pre-order traversal.

>>> tree = BTNode(1, BTNode(2, None, BTNode(3)), BTNode(4))
>>> tree.flattened_pre_order()
[1, 2, 3, 4]
>>> node = BTNode(9999)
>>> for i in range(9998, -1, -1): node = BTNode(i, node)
>>> node.flattened_pre_order() == list(range(10000))
True

"""
result = []
stack = [self]
node = None
while stack:
if node is None:
node = stack.pop()
if node is not None:
result.append(node.item)
stack.append(node.right)
node = node.left
return result


Rather than building up a list and returning it, consider implementing a generator instead. Then you could "yield" each self.item. If the result is going to be processed one at a time and the result is a very long list you save the expense of building up that long list.

def __iter__(self):
''' Pre-order iterator '''
yield self.item
if self.left:
for item in self.left:
yield item
if self.right:
for item in self.right:
yield item


Furthermore, you can easily reimplement the original function by taking advantage of the generator:

def number(self: 'BTNode') -> list:
''' Pre-order traversal '''
return list(self)