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


def build_avl(elements, i, j, height):
    if i > j:
        return None, height - 1
    mid = (i + j) // 2
    root = Node(elements[mid])
    root.left, height_left = build_avl(elements, i, mid - 1, height + 1)
    root.right, height_right = build_avl(elements, mid + 1, j, height + 1)
    if height_left > height_right:
        height = height_left
    else:
        height = height_right
    return root, height


def print_pre_order(node):
    print(node.value)
    if node.left is not None:
        print_pre_order(node.left)
    if node.right is not None:
        print_pre_order(node.right)


def rotate_right(node):
    p = node.left
    node.left = p.right
    p.right = node
    node = p
    return node

def build_backbone(root):
    node = root
    while node is not None:
        print_pre_order(node)
        print('--------')
        if node.left is not None:
            node = rotate_right(node)
        else:
            node = node.right
    return root


def dsw(root, n):
    old_root = root
    new_root = old_root.right
    while new_root is not None:
        if new_root.left is None:
            old_root = new_root
            new_root = new_root.right
        else:
            tmp_node = new_root.left
            new_root.left = tmp_node.right
            tmp_node.right = new_root
            new_root = tmp_node
            old_root.right = tmp_node


numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
print(numbers)
tree_root, tree_height = build_avl(numbers, 0, len(numbers) - 1, 0)
print("przed zbudowaniem kregoslupa:")
print_pre_order(tree_root)
print('--------')
tree_root = build_backbone(tree_root)
print("po zbudowaniu kregoslupa:")
print_pre_order(tree_root)