Get Breadth First (Level) Order Without Constructing Red-Black Tree

user_2955541 0
Viewed 61

I have an ordered array of length n containing consecutive integer elements 1 to n. After constructing the red-black tree for this array, I can traverse this tree in level order using a standard breadth first search approach.

My question is, given any n <= 100000000 (corresponding to an ordered array with consecutive integer elements from 1 to n), is it possible to bypass the construction of the tree and directly return the level order?

binary-search-tree breadth-first-search algorithm
1 Answers

If you don't mind extra space, you can do this.

def level_order(n):
    queue = [(1, n)]
    i = 0
    while i < len(queue):
        a, b = queue[i]
        i += 1
        if a > b:
            continue
        m = (a + b) // 2
        yield m
        queue.append((a, m - 1))
        queue.append((m + 1, b))


print(list(level_order(13)))
user_21446690
Related