How to implement 'range' with a python BST

Question

My code at the moment allows me to search for a specific node, I would like to edit it so that I can search within a range of numbers. For example, I have a price list of apples, and I would like to add all apples to a list/dictionary that cost between $2-$4 or something like that.

Here is my current code

def valueOf(self, key):
    node = self._bstSearch(self._root, key)
    assert node is not None, "Invalid map key."
    return node.value

def _bstSearch(self, subtree, target):
    if subtree is None:
        return None
    elif target < subtree.key:
        return self._bstSearch( subtree.left, target)
    elif target > subtree.key:
        return self._bstSearch(subtree.right, target)
    else:    
        return subtree

I think I should be editing target to change it from a single item search to a ranged item search but I'm not 100% sure how to

Mikhail M. · Accepted Answer · 2016-10-16 10:49:17Z

3

Using recursive in-order traversal:

def range(self, a, b):
    return self._traverse_range(self._root, a, b)

def _traverse_range(self, subtree, a, b, cumresult=None):
    if subtree is None:
        return

    # Cumulative variable.
    if cumresult is None:
        cumresult = []

    # Traverse LEFT subtree if it is possible to find values in required range there.
    if subtree.key > a:
        self._traverse_range(subtree.left, a, b, cumresult)

    # Push VALUE if it is in our range.
    if a <= subtree.key <= b:  # Change to strict "< b" to act like python's range
        cumresult.append(subtree.key)

    # Traverse RIGHT subtree if it is possible to find values in required range there.
    if subtree.key < b:
        self._traverse_range(subtree.right, a, b, cumresult)

    return cumresult

edited Oct 16, 2016 at 10:49

answered Oct 16, 2016 at 8:30

Mikhail M.

6,0883 gold badges26 silver badges32 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Ben Over a year ago

I was looking for a particular implementation for a range tree to perform efficient range queries in python, then found this answer and added it to this AVL Tree implementation (automatically self-rebalancing BST): gist.github.com/girish3/a8e3931154af4da89995 (python2 but only with the print function). To make these functions work with the AVL Tree, change the self._root to self.node and subtree.{left,right} to subtree.{left, right}.node. Works like a charm!

Collectives™ on Stack Overflow

How to implement 'range' with a python BST

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related