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

def stretch(root, stretch_amount):
    return stretch_left(root, stretch_amount)


def stretch_left(root, stretch_amount):
    target_value = int(root.value / stretch_amount)
    right = root.right
    left = root.left

    root.value = target_value
    root.right = None
    root.left = None
    prev = root

    for i in range(stretch_amount-1):
        node = Node(target_value)
        prev.left = node
        prev = node

    prev.left = left
    prev.right = right

    if prev.left:
        prev.left = stretch_left(prev.left, stretch_amount)

    if prev.right:
        prev.right = stretch_right(prev.right, stretch_amount)

    return root

def stretch_right(root, stretch_amount):
    target_value = int(root.value / stretch_amount)
    right = root.right
    left = root.left

    root.value = target_value
    root.right = None
    root.left = None
    prev = root

    for i in range(stretch_amount-1):
        node = Node(target_value)
        prev.right = node
        prev = node

    prev.left = left
    prev.right = right

    if prev.left:
        prev.left = stretch_left(prev.left, stretch_amount)

    if prev.right:
        prev.right = stretch_right(prev.right, stretch_amount)

    return root

def print_tree(root):
    if root is None:
        return

    print(root.value)
    print('------')
    print_tree(root.left)
    print_tree(root.right)


root = Node(12)
eighty1 = Node(81)
thirty4 = Node(34)
fifty6 = Node(56)
nineteen = Node(19)
six = Node(6)

root.left = eighty1
root.right = thirty4
eighty1.right = fifty6
thirty4.left = nineteen
thirty4.right = six

# import ipdb
# ipdb.set_trace()

new_tree = stretch(root, 3)
print_tree(new_tree)