Ok, thanks @ecolban, it is fixed now. I just could not understand the random test, but looking at the structure of your ascii tree it makes sense now.

My problem was indeed that I popped from the input array a (sorry @Blind4Basics !)

No, I made a copy before passing to my function:
tree = a.copy()

I just don't get how the last test can work (unless the random seed is the same each time):
Test.it('Random ten nodes')
a = [randrange(10) for i in range(10)]
Test.assert_equals(complete_binary_tree(a), [a[i] for i in [6, 3, 8, 1, 5, 7, 9, 0, 2, 4]])

Yes, sorry. In the last python test I get this error with exit code 1:

Traceback (most recent call last):
File "main.py", line 13, in
Test.assert_equals(complete_binary_tree(a), [a[i] for i in [6, 3, 8, 1, 5, 7, 9, 0, 2, 4]])
File "main.py", line 13, in
Test.assert_equals(complete_binary_tree(a), [a[i] for i in [6, 3, 8, 1, 5, 7, 9, 0, 2, 4]])
IndexError: list index out of range

Thanks!

I tweaked the same algorithm and submitted as Javascript, which worked.
Please fix the last Python test case.

Why is this marked fixed. My python test is failing on the random test.

Why is this marked fixed. My python test is failing on the random test.