class BT_Array_BFS:
    def __init__(self, tree):
        self.tree = tree

    def traverse_levelorder_bfs(self):
        if len(self.tree) == 0:
            return
        q = []

        # initialization
        i_root = 0
        q.append(i_root)

        while(True):
            if len(q) == 0 :
                break

            i = q.pop(0)
            if i>=len(tree) :
                continue
            if tree[i] == None :
                continue

            print(tree[i], end=" ")

            # get left right index
            i_plus_one = i + 1
            i_left_plus_one = i_plus_one * 2
            i_right_plus_one = i_plus_one * 2 + 1

            i_left = i_left_plus_one - 1
            i_right = i_right_plus_one - 1

            q.append(i_left)
            q.append(i_right)


if __name__=='__main__':

    # build binary tree
    tree = [
            5,
            2, 6,
            1, 4, None, 7,
            None, None, 3, None, None, None, None, None
    ]
    bt_array_bfs = BT_Array_BFS(tree)
    print()

    # traverse (BFS)
    print("level-order: ")
    bt_array_bfs.traverse_levelorder_bfs()
    print()