We have mentioned how to search for a node on a BST. One other practical query is to search for nodes with keys fall in a specific range. For example, below is a BST, 10 / \ 8 13 / \ / \ 7 9 11 14 Given an input range [9, 13] (both ends are inclusive), we want to return the nodes [9, 10, 11, 13] (in the sorted order). Implement the function range_search(bst, range). You should copy and past the previous implementation of BST here.

Sure, here's the previous implementation of BST:

class Node:
    def __init__(self, key):
        self.left = None
        self.right = None
        self.val = key

class BST:
    def __init__(self):
        self.root = None

    def insert(self, key):
        self.root = self._insert(self.root, key)

    def _insert(self, node, key):
        if node is None:
            return Node(key)
        else:
            if key < node.val:
                node.left = self._insert(node.left, key)
            else:
                node.right = self._insert(node.right, key)
        return node

    def search(self, key):
        return self._search(self.root, key)

    def _search(self, node, key):
        if node is None or node.val == key:
            return node
        elif key < node.val:
            return self._search(node.left, key)
        else:
            return self._search(node.right, key)

And here's the implementation of `range_search`:

def range_search(bst, r):
    result = []
    _range_search(bst.root, r[0], r[1], result)
    return result

def _range_search(node, min_val, max_val, result):
    if node is None:
        return
    if min_val <= node.val <= max_val:
        _range_search(node.left, min_val, max_val, result)
        result.append(node.val)
        _range_search(node.right, min_val, max_val, result)
    elif node.val < min_val:
        _range_search(node.right, min_val, max_val, result)
    else:
        _range_search(node.left, min_val, max_val, result)

The `range_search` function takes a BST and a range `r` as input. It initializes an empty list `result` which will contain the nodes within the range.

`_range_search` is a recursive helper function. It takes a node, a minimum value `min_val`, a maximum value `max_val`, and the `result` list as input. If the node is within the range, it recursively calls itself on the left and right subtrees, adds the node's value to the result list, and then recursively calls itself on the left and right subtrees again. If the node's value is less than the minimum value of the range, it only recursively calls itself on the right subtree. If the node's value is greater than the maximum value of the range, it only recursively calls itself on the left subtree.

Finally, the `range_search` function calls `_range_search` on the root node of the BST and returns the result list.