#######################- Printing -#################################
	
# Display List Code Below:
def height(node):
	if (node == None):
		return 0
	return 1 + max(height(node.left), height(node.right))

def draw_node(output, link_above, node, level, p, link_char):
	if (node == None): 
 		return

	out = "["
	h = len(output)
	SP = " "

	if (p < 0):
		for s in output:
			if (s):
				s = " "*(-1*p) + s
    
		for s in link_above:
			if (s):
				s = " "*(-1*p) + s

	if level < h - 1:
		p = max(p, len(output[level + 1]))
	if (level > 0):
		p = max(p, len(output[level - 1]))
	p = max(p, len(output[level]))

	# Fill in to left
	if (node.left):
		leftData = SP + str(node.left.data) + SP
		draw_node(output, link_above, node.left, level + 1, p - len(leftData),'L')
		p = max(p, len(output[level + 1]))

	# Enter this data
	space = p - len(output[level])
	if (space > 0):
		output[level] += (' ' * space)
	node_data = SP + str(node.data) + SP
	output[level] += node_data

	# Add vertical link above
	space = p + len(SP) - len(link_above[level])
	if (space > 0):
		link_above[level] += (' ' * space)
	link_above[level] += link_char

	# Fill in to right
	if (node.right):
		draw_node(output, link_above, node.right, level + 1, len(output[level]),'R')
  
def display_tree(root):
	if (root == None):
		print("\tNone")
	h = height(root)
	output = []
	link_above = []
	for i in range(0,h): 
				output.append("")
				link_above.append("")
	draw_node(output, link_above, root, 0, 5, ' ')

	# Create link lines
	for i in range(h):
		for j in range(len(link_above[i])):
			if (link_above[i][j] != ' '):
				size = len(output[i - 1])
				if (size < j + 1):
					output[i - 1] += " " *(j + 1 - size)
				jj = j
				if (link_above[i][j] == 'L'):
					while (output[i - 1][jj] == ' '):
						jj += 1
					for k in range(j+1, jj-1):
						str1 = output[i - 1]
						list1 = list(str1)
						list1[k] = '_'
						output[i - 1] = ''.join(list1)
				elif(link_above[i][j] == 'R'):
					while (output[i - 1][jj] == ' '):
						jj-=1
					
					# k = j-1
					for k in range(j-1,jj+1,-1):
						temp = output[i - 1]
						list1 = list(temp)
						list1[k] = '_'
						output[i - 1] = ''.join(list1)
						k = k - 1
      
				str1 = link_above[i]
				list1 = list(str1)
				list1[j] = '|'
				link_above[i] = ''.join(list1)
					
	# Output
	for i in range(h):
		if (i):
			print("\t" , link_above[i])
		print("\t" , output[i])from BinaryTree import *
from TreeNode import *

# Initializing our marker
MARKER = "M"
m = 1


def serialize_rec(node, stream):
    global m
    # Adding marker to stream if the node is None
    if node is None:
        stream.append(MARKER + str(m))
        m += 1
        return

    # Adding node to stream
    stream.append(node.data)

    # Doing a pre-order tree traversal for serialization
    serialize_rec(node.left, stream)
    serialize_rec(node.right, stream)

# Function to serialize tree into list of integers.
def serialize(root):
    stream = []
    serialize_rec(root, stream)
    return stream

def deserialize_helper(stream):
    # pop last element from list
    val = stream.pop()

    # Return None when a marker is encountered
    if type(val) is str and val[0] == MARKER:
        return None

    # Creating new Binary Tree Node from current value from stream
    node = TreeNode(val)

    # Doing a pre-order tree traversal for deserialization
    node.left = deserialize_helper(stream)
    node.right = deserialize_helper(stream)

    # Return node if it exists
    return node

# Function to deserialize integer list into a binary tree.
def deserialize(stream):
    stream.reverse()
    node = deserialize_helper(stream)
    return node

# driver code
def main():
    global m
    input_trees = [
        [TreeNode(100), TreeNode(50), TreeNode(200), TreeNode(25), TreeNode(75), TreeNode(350)],
        [TreeNode(100), TreeNode(200), TreeNode(75), TreeNode(50), TreeNode(25), TreeNode(350)],
        [TreeNode(200), TreeNode(350), TreeNode(100), TreeNode(75), TreeNode(50), TreeNode(200), TreeNode(25)],
        [TreeNode(25), TreeNode(50), TreeNode(75), TreeNode(100), TreeNode(200), TreeNode(350)],
        [TreeNode(350), TreeNode(75), TreeNode(25), TreeNode(200), TreeNode(50), TreeNode(100)],
        [TreeNode(1), None, TreeNode(2), None, TreeNode(3), None, TreeNode(4), None, TreeNode(5)]
    ]

    indx = 1
    for i in input_trees:
        tree = BinaryTree(i)

        print(indx, ".\tBinary Tree:", sep="")
        indx += 1
        if tree.root is None:
            display_tree(None)
        else:
            display_tree(tree.root)

        print("\n\tMarker used for NULL nodes in serialization/deserialization: ",
              MARKER, "*", sep="")

        # Serialization
        ostream = serialize(tree.root)
        print("\n\tSerialized integer list:")
        print("\t" + str(ostream))

        # Deserialization
        deserialized_root = deserialize(ostream)
        print("\n\tDeserialized binary tree:")
        display_tree(deserialized_root)
        print("-"*100)
        m = 1


if __name__ == '__main__':
    main()