Python deque from collections is not deterministic with order; repeated executions give different results

Question

from collections import deque

class Node(object):
    def __init__(self,val):
        self.value = val
        self.right = None
        self.left = None

class Btree:
    def __init__(self):
        self.root = None

    def btree_print(self):
        if self.root:
            print("Values of btree are")
            q = deque()
            q.append(self.root)
            q.append(None)

            while q:
                parent = q.popleft()
                if parent is None:
                    print("End of  a Level")
                    if q:
                        q.append(None)
                    continue

                print("Value of btree Elm:", parent.value)

                for child in {parent.left, parent.right}:
                    if child:
                        q.append(child)

        else:
            print("Btree Empty")

    def btree_insert_helper(self, val):
        q = deque()
        q.append(self.root)

        while q:
            node = q.popleft()
            for child in {node.left, node.right}:
                if child:
                    q.append(child)
                elif node.left:
                    node.right = Node(val)
                    return
                else:
                    node.left = Node(val)
                    return

    def btree_insert(self, val):
        if self.root:
            self.btree_insert_helper(val)
        else:
            self.root = Node(val)

btree = Btree()
btree.btree_insert(1)
btree.btree_insert(2)
btree.btree_insert(3)
btree.btree_insert(4)
btree.btree_insert(5)
btree.btree_insert(6)
btree.btree_insert(7)

btree.btree_print()

In the above program, if I execute it multiple times it's giving me different results; I am seeing 2 different orders. Regardless of logic, the result should be always same as its a single threaded program. I'm not sure why order is being changed.

Expected result, Order1:

Values of btree are
Value of btree Elm: 1
End of  a Level
Value of btree Elm: 2
Value of btree Elm: 3
End of  a Level
Value of btree Elm: 4
Value of btree Elm: 5
Value of btree Elm: 6
Value of btree Elm: 7
End of  a Level

Not expected but sometimes programme is giving following result (4, 5 is flipped to 5, 4), Order2:

Values of btree are
Value of btree Elm: 1
End of  a Level
Value of btree Elm: 2
Value of btree Elm: 3
End of  a Level
Value of btree Elm: 5
Value of btree Elm: 4
Value of btree Elm: 6
Value of btree Elm: 7
End of  a Level

any help would be greatly appreciated

Answer 1

The binary tree itself is consistent. The reason that your print order is inconsistent comes from the line:

for child in {parent.left, parent.right}:

This is iterating over a set of {parent.left, parent.right}. Sets do not have order so you could iterate either left then right or right then left.

Changing it to:

for child in (parent.left, parent.right):

will make it print consistently.