6
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ I think number would be better named enumerate. \$\endgroup\$ – 200_success Dec 28 '13 at 18:56
4
\$\begingroup\$
  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
    
\$\endgroup\$
1
\$\begingroup\$

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)
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.