2 Added recursive solution
source | link

If the nodes contain a max_end attribute in addition to the interval, you can use the max_end to stop looking further down the tree.

def find_containing_intervals(interval, root_node):
    stack = [root_node]
    containing_intervals = []
    while stack:
        node = stack.pop()
        if node is None:
            continue
        if node.max_end < interval.end:
            continue
        if node.interval.contains(interval):
            containing_intervals.append(interval)
        if node.interval.start <= interval.start:
            stack.append(node.right_child)
        stack.append(node.left_child)

    return containing_intervals

Recursive solution:

class Node:
    def find_containing(self, interval):
        intervals = []
        if self.max_end < interval.end:
            return intervals
        if self.interval.contains(interval):
            intervals.append(interval)
        if self.right_child is not None and self.interval.start <= interval.start:
            intervals.extend(self.right_child.find_containing(interval))
        if self.left_child is not None:
            intervals.extend(self.left_child.find_containing(interval))
        return intervals

If the nodes contain a max_end attribute in addition to the interval, you can use the max_end to stop looking further down the tree.

def find_containing_intervals(interval, root_node):
    stack = [root_node]
    containing_intervals = []
    while stack:
        node = stack.pop()
        if node is None:
            continue
        if node.max_end < interval.end:
            continue
        if node.interval.contains(interval):
            containing_intervals.append(interval)
        if node.interval.start <= interval.start:
            stack.append(node.right_child)
        stack.append(node.left_child)

    return containing_intervals

If the nodes contain a max_end attribute in addition to the interval, you can use the max_end to stop looking further down the tree.

def find_containing_intervals(interval, root_node):
    stack = [root_node]
    containing_intervals = []
    while stack:
        node = stack.pop()
        if node is None:
            continue
        if node.max_end < interval.end:
            continue
        if node.interval.contains(interval):
            containing_intervals.append(interval)
        if node.interval.start <= interval.start:
            stack.append(node.right_child)
        stack.append(node.left_child)

    return containing_intervals

Recursive solution:

class Node:
    def find_containing(self, interval):
        intervals = []
        if self.max_end < interval.end:
            return intervals
        if self.interval.contains(interval):
            intervals.append(interval)
        if self.right_child is not None and self.interval.start <= interval.start:
            intervals.extend(self.right_child.find_containing(interval))
        if self.left_child is not None:
            intervals.extend(self.left_child.find_containing(interval))
        return intervals
1
source | link

If the nodes contain a max_end attribute in addition to the interval, you can use the max_end to stop looking further down the tree.

def find_containing_intervals(interval, root_node):
    stack = [root_node]
    containing_intervals = []
    while stack:
        node = stack.pop()
        if node is None:
            continue
        if node.max_end < interval.end:
            continue
        if node.interval.contains(interval):
            containing_intervals.append(interval)
        if node.interval.start <= interval.start:
            stack.append(node.right_child)
        stack.append(node.left_child)

    return containing_intervals