Invert Binary Tree

def invertTree(tree):
    n = len(tree)
    size = 1
    while size < n:  # round up to whole levels, so every mirrored index fits
        size = 2 * size + 1
    out = [-1] * size

    def place(src, dst):
        if src >= n or tree[src] == -1:
            return
        out[dst] = tree[src]
        place(2 * src + 1, 2 * dst + 2)  # the left subtree goes to the right
        place(2 * src + 2, 2 * dst + 1)  # the right subtree goes to the left

    place(0, 0)
    last = size - 1
    while out[last] == -1:  # trim the trailing -1 entries
        last -= 1
    return out[:last + 1]

def invertTree(tree):
    n = len(tree)
    size = 1
    while size < n:  # round up to whole levels, so every mirrored index fits
        size = 2 * size + 1
    out = [-1] * size
    queue = [(0, 0)]  # pairs: index in tree, index of its mirrored spot in out
    head = 0
    while head < len(queue):
        src, dst = queue[head]
        head += 1
        out[dst] = tree[src]
        left, right = 2 * src + 1, 2 * src + 2
        if left < n and tree[left] != -1:
            queue.append((left, 2 * dst + 2))  # the left child goes to the right
        if right < n and tree[right] != -1:
            queue.append((right, 2 * dst + 1))  # the right child goes to the left
    last = size - 1
    while out[last] == -1:  # trim the trailing -1 entries
        last -= 1
    return out[:last + 1]