Tell me more ×
Stack Overflow is a question and answer site for professional and enthusiast programmers. It's 100% free, no registration required.
up vote 1 down vote favorite

Given a Binary Search Tree, for example:

        9
            8
    7
5
    3
        2

I would like to get an in-order list of nodes with values between a and b (inclusive).

I have implemented a recursive helper function:

def _range(root, a, b):
node_list = []
if root.left:
    node_list.append(_range(root.left, a, b))
if root.value >= a and root.value <= b:
    node_list.append(root)
if root.right:
    node_list.append(_range(root.right, a, b))
return node_list

Which gives me:

[[[BTNode: 2], BTNode: 3], BTNode: 5, [BTNode: 7, [[BTNode: 8], BTNode: 9]]]

I however need:

[BTNode: 2, BTNode: 3, BTNode: 5, BTNode: 7, BTNode: 8, BTNode: 9]

Is there anyway to flatten the list? I realize that what I am doing is appending a list to another list, but am not sure how to fix this without breaking the code.

share|improve this question
2  
Did you try to use node_list.extend instead of node_list.append? An other solution would be to pass the list as parameter. –  Bakuriu Nov 6 '12 at 17:56
1  
It took me a while to figure out that your tree is drawn from left to right instead of top to down. That was quite confusing… ^^ –  poke Nov 6 '12 at 17:58

1 Answer

up vote 0 down vote

append adds the object that you pass as argument to the list, so you obviously end up with nested lists. You want to concatenate the results, so you want to use list.extend(or the += operator):

>>> from collections import namedtuple
>>> class Node(namedtuple('Node', 'value left right')):
...     # I reimplement __str__ just to avoid too much output later
...     def __repr__(self):
...             return 'Node(%r)' % self.value
...     __str__ = __repr__
... 
>>> def make_node(value, left=None, right=None):
...     return Node(value, left, right)
... 
>>> def _range(root, a, b):
...     node_list = []
...     if root.left:
...             node_list.extend(_range(root.left, a, b))
...     if a <= root.value <= b:
...             node_list.append(root)
...     if root.right:
...             node_list.extend(_range(root.right, a, b))
...     return node_list
... 
>>> tree = make_node(5, make_node(3, make_node(2)), make_node(7, None, make_node(8, None, make_node(9))))
>>> _range(tree, 1, 3)
[Node(2), Node(3)]
>>> _range(tree, 1, 10)
[Node(2), Node(3), Node(5), Node(7), Node(8), Node(9)]

An other way of doing it would be to pass the list around as a parameter:

>>> def _range(root, a, b, node_list=None):
...     if node_list is None:
...             # Note: do *not* use "[]" as a default!
...             node_list = []
...     if root.left:
...             _range(root.left, a, b, node_list)
...     if a <= root.value <= b:
...             node_list.append(root)
...     if root.right:
...             _range(root.right, a, b, node_list)
...     return node_list
... 
>>> _range(tree, 1, 3)
[Node(2), Node(3)]
>>> _range(tree, 1, 10)
[Node(2), Node(3), Node(5), Node(7), Node(8), Node(9)]
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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