return chain.from_iterable(combinations(s, r) for r in range(len(s) + 1))

def traversals(tree):
    left, mid, right = tree.lefts[0].name, tree.name, tree.rights[0].name
nodes = list(inorder(tree))
l_i, m_i, r_i = [nodes.index(x) for x in (left, mid, right)]
parts = nodes[:l_i], nodes[l_i + 1:m_i], nodes[m_i + 1:r_i], nodes[r_i + 1:]
psets = [powerset(x) for x in parts]
for p1, p2, p3, p4 in product(*psets):
    yield ''.join(chain(p1, left, p2, mid, p3, right, p4))
print(list(traversals(tree)))
How to iterate this tree/graph