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

-
There is no docstring for the number method.

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

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

-
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.

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

-
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.

-
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.

-
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 "", line 1, in 
  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

StackExchange Code Review Q#33662, answer score: 5