print_tree

FIELD_WIDTH = 3


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


def get_height(node):
    return 0 if not node else 1 + max(get_height(node.left), get_height(node.right))


def update_output(node, row, left, right, output):
    if not node:
        return
    mid = (left + right) // 2
    output[row][mid] = str(node.value).center(FIELD_WIDTH)
    update_output(node.left, row + 1, left, mid - 1, output)
    update_output(node.right, row + 1, mid + 1, right, output)


def get_lines(root):
    height = get_height(root)
    width = 2 ** height - 1
    output = [[' ' * FIELD_WIDTH] * width for i in range(height)]
    update_output(node=root, row=0, left=0, right=width - 1, output=output)
    return output


def get_size(node):
    if not node:
        return 0
    node.size = 1 + get_size(node.left) + get_size(node.right)
    return node.size


def print_tree(root):
    if not root:
        print(None)
    [print(''.join(line)) for line in get_lines(root)]


node1 = Node(1)
node3 = Node(3)
# 5 7 9 11 13 15
node5 = Node(5)
node7 = Node(7)
node9 = Node(9)
node11 = Node(11)
node13 = Node(13)
node15 = Node(15)
node2 = Node(2, node1, node3)
# 6 10 14
node6 = Node(6, node5, node7)
node10 = Node(10, node9, node11)
node14 = Node(14, node13, node15)
# 4 12
node4 = Node(4, node2, node6)
node12 = Node(12, node10, node14)
root = Node(8, node4, node12)

print_tree(root)