Python Tree Traversal - BFS and DFS( inorder - preorder - postorder )

traverse.py

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None
    def __repr__(self):
        return str(self.value)
class Tree:
    def __init__(self):
        self.root = Node(0)
MaxValue = 14
t = Tree()
head = t.root
i = 1
q = [head]
while q:
    c = q.pop(0)
    c.left = Node(i)
    c.right = Node(i+1)
    i+=2
    if i <=MaxValue//2:
        q.extend([c.left, c.right])

# BFS
q = [head]
t = ""
while q:
    c = q.pop(0)
    if c.left:
        q.append(c.left)
    if c.right:
        q.append(c.right)
    t+= str(c.value) + "-"
print("BFS", t)

# DFS
t = ""
q = [head]
while q:
    c = q.pop(0)
    q2 = []
    if c.left:
        q2.append(c.left)
    if c.right:
        q2.append(c.right)
    q = q2 + q
    t += str(c.value) + "-"
print("DFS preorder", t)

# DFS
t = ""
q = [head]
seen = [False] * (MaxValue+1)
while q:
    c = q.pop(0)
    q2 = []
    if c.left:
        q2.append(c.left)
    if c.right:
        q2.append(c.right)
    if not c.left or seen[c.value]:
        t += str(c.value) + "-"
    else:
        q = [q2[0], c ,q2[1]] + q
    seen[c.value] = True
print("DFS inorder", t) 
# DFS
t = ""
q = [head]
seen = [False] * (MaxValue+1)
while q:
    c = q.pop(0)
    q2 = []
    if c.left:
        q2.append(c.left)
    if c.right:
        q2.append(c.right)
    if not c.left and not c.right or seen[c.value]:
        t += str(c.value) + "-"
    else:
        q = [q2[0], q2[1], c] + q
    seen[c.value] = True

print("DFS postorder", t)