class BST:
    class Node:
        def __init__(self, data):
            self.data = data
            self.left = None
            self.right = None

    def __init__(self, arr=None):
        self.root = None

    def __eq__(self, other):
        return (str(self) == str(other))

    def __repr__(self):
          return str(self.preorder())

    def preorder(self):
        def preorder_node(node):
            if(node is None):
                return
            yield node.data
            yield from preorder_node(node.left)
            yield from preorder_node(node.right)
        return tuple(preorder_node(self.root))

    def __hash__(self):
        return hash(str(self))

    def insert(self, data):
        node = self.root
        if(node is None):
            self.root = BST.Node(data)
            return
        while True:
            if(data < node.data):
                if(node.left != None):
                    node = node.left
                else:
                    node.left = BST.Node(data)
                    return
            elif(data > node.data):
                if(node.right != None):
                    node = node.right
                else:
                    node.right = BST.Node(data)
                    return

    def avl(self):
        def equal_depth_node(node):
            if abs(BST.max_depth(node.left)-BST.max_depth(node.right)) > 1:
                return False
            return True
        def avl_node(node):
            if(node is None):
                return True
            else:
                l = avl_node(node.left)
                r = avl_node(node.right)
                mdl = equal_depth_node(node)
                return l and r and mdl
        return avl_node(self.root)

    def max_depth(node):
        def depth(node,d):
            if(node is None):
                return d
            return max(depth(node.left,d+1),depth(node.right,d+1))
        return depth(node,0)

class AVLSet:
    def __init__(self):
        self.set = set()

    def add(self, seq):     # postupnost dat na vytvorenie stromu
        t = BST()           # prida do mnoziny, len ak podmienka avl
        for prvok in seq:
            t.insert(prvok)
            if(t.avl() == False):
                return
        if(t.avl()):
            self.set.add(t)

    def __iter__(self):
        yield from self.set

    def __len__(self):
        return len(self.set)

    def all(self, seq):                                 #postupne vygeneruje vsetky permutacie postupnosti
        seqs = AVLSet.sequences(seq)                    # vyrobi stromy a prida do mnoziny, len ak podmienka avl
        for s in seqs:
            self.add(s)

    def sequences(seq):
##        def vkladaj(prvok, postupnosti):
##            if(postupnosti is None):
##                tuplik = tuple(prvok)
##                return [tuplik]
##            else:
##                vysl = []
##                for post in postupnosti:
##                    for i in range(len(post)):
##                        pom = list(post)
##                        pom.insert(prvok, i)
##                        vysl.append(tuple(pom))
##        if(len(seq) == 1):
##            return [seq]
##        else:
##            return vkladaj(seq[0],AVLSet.sequences(seq[1:]))
        return [()]

if __name__ == '__main__':
    t1 = BST()
    for i in (1, 2, 3, 4):
        t1.insert(i)
    print(t1)
    print('avl =', t1.avl())
    t2 = BST()
    for i in (2, 4, 3, 1):
        t2.insert(i)
    print(t2)
    print('avl =', t2.avl())
    t3 = BST()
    for i in (2, 1, 4, 3):
        t3.insert(i)
    print('eq =', t2 == t3)
    mn = AVLSet()
    mn.add((1, 2, 3, 4))
    mn.add((2, 4, 3, 1))
    mn.add((2, 1, 4, 3))
    mn.add((2, 4, 1, 3))
    print('set:')
    for t in mn:
        print(t)
    print('all:')
    mn = AVLSet()
    mn.all((1, 2, 3, 4))
    print(*mn, sep='\n')
    mn = AVLSet()
    mn.all(range(5))
    print('all range(5) =', len(mn))