import timeit

class Tree:
    def __init__(self, left, value, right):
        self.left = left
        self.value = value
        self.right = right


    def __iter__(self):
        if self.left:
            for item in self.left:
                yield item
        yield self.value
        if self.right:
            for item in self.right:
                yield item

def tree(input: range) -> Tree | None:
    n = len(input)
    if n == 0:
        return None
    i = n // 2
    return Tree(tree(input[:i]), input[i], tree(input[i + 1:]))

def setup():
    global iterable
    assert list(tree(range(10))) == list(range(10))
    iterable = tree(range(100000))
    
print(timeit.timeit("for _ in iterable: pass", "setup()", globals=globals(), number=10))

import timeit

class RangeWrapper:
    def __init__(self, n):
        self.r = range(n)

    def __iter__(self):
        for item in self.r:
            yield item

def setup():
    global iterable
    iterable = RangeWrapper(1000000)

print(timeit.timeit("for _ in iterable: pass", "setup()", globals=globals(), number=10))