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


def serialize(root):
    nodes = []
    curr_q = [root]
    next_level = True if root else False
    while next_level and curr_q:
        next_q = []
        next_level = False
        for node in curr_q:
            if node:
                nodes.append(str(node.val))
                if node.left or node.right:
                    next_level = True
                next_q.append(node.left)
                next_q.append(node.right)
            else:
                nodes.append(str(node))
        curr_q = next_q
        next_q = []

    return ','.join(nodes)


def deserialize(tree):
    if not tree:
        return None

    nodes = [None if n == 'None' else int(n) for n in tree.split(',')]
    root = Node(nodes.pop(0))
    curr_q = [root]
    while nodes and curr_q:
        parent = curr_q.pop(0)
        left_node = nodes.pop(0)
        if left_node != None:
            parent.left = Node(left_node)
            curr_q.append(parent.left)

        right_node = nodes.pop(0)
        if right_node != None:
            parent.right = Node(right_node)
            curr_q.append(parent.right)

    return root


def display_tree(root):
    if not root:
        return

    level = 0
    curr_q = [root]
    print_line = True
    while print_line and curr_q:
        print_line = False
        next_q = []
        level += 1
        print('Level:', level)
        for node in curr_q:
            if node == None:
                print('None', end=',')
            else:
                print(node.val, end=',')
                next_q.append(node.left)
                next_q.append(node.right)
                if node.left or node.right:
                    print_line = True
        print('')

        curr_q = next_q


# test 1
print('Test 1')
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.right.left = Node(4)
root.right.right = Node(5)

serialized_tree = serialize(root)
assert serialized_tree == '1,2,3,None,None,4,5'
deserialized_tree = deserialize(serialized_tree)
display_tree(deserialized_tree)
print('')

# test 2
print('Test 2')
root = Node(1)
serialized_tree = serialize(root)
assert serialized_tree == '1'
deserialized_tree = deserialize(serialized_tree)
display_tree(deserialized_tree)
print('')

# test 3
print('Test 3')
root = None
serialized_tree = serialize(root)
assert serialized_tree == ''
deserialized_tree = deserialize(serialized_tree)
display_tree(deserialized_tree)
print('')

# test 4
print('Test 4')
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)

serialized_tree = serialize(root)
assert serialized_tree == '1,2,3,4,5,None,None'
deserialized_tree = deserialize(serialized_tree)
display_tree(deserialized_tree)
print('')

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


def serialize(root):
    nodes = []
    curr_q = [root]
    next_level = True if root else False
    while next_level and curr_q:
        next_q = []
        next_level = False
        for node in curr_q:
            if node:
                nodes.append(str(node.val))
                if node.left or node.right:
                    next_level = True
                next_q.append(node.left)
                next_q.append(node.right)
            else:
                nodes.append(str(node))
        curr_q = next_q
        next_q = []

    return ','.join(nodes)


def deserialize(tree):
    if not tree:
        return None

    nodes = [None if n == 'None' else int(n) for n in tree.split(',')]
    root = Node(nodes.pop(0))
    curr_q = [root]
    while nodes and curr_q:
        parent = curr_q.pop(0)
        left_node = nodes.pop(0)
        if left_node != None:
            parent.left = Node(left_node)
            curr_q.append(parent.left)

        right_node = nodes.pop(0)
        if right_node != None:
            parent.right = Node(right_node)
            curr_q.append(parent.right)

    return root


def display_tree(root):
    if not root:
        return

    level = 0
    curr_q = [root]
    print_line = True
    while print_line and curr_q:
        print_line = False
        next_q = []
        level += 1
        print('Level:', level)
        for node in curr_q:
            if node == None:
                print('None', end=',')
            else:
                print(node.val, end=',')
                next_q.append(node.left)
                next_q.append(node.right)
                if node.left or node.right:
                    print_line = True
        print('')

        curr_q = next_q


# test 1
print('Test 1')
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.right.left = Node(4)
root.right.right = Node(5)

serialized_tree = serialize(root)
assert serialized_tree == '1,2,3,None,None,4,5'
deserialized_tree = deserialize(serialized_tree)
display_tree(deserialized_tree)
print('')

# test 2
print('Test 2')
root = Node(1)
serialized_tree = serialize(root)
assert serialized_tree == '1'
deserialized_tree = deserialize(serialized_tree)
display_tree(deserialized_tree)
print('')

# test 3
print('Test 3')
root = None
serialized_tree = serialize(root)
assert serialized_tree == ''
deserialized_tree = deserialize(serialized_tree)
display_tree(deserialized_tree)
print('')

# test 4
print('Test 4')
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)

serialized_tree = serialize(root)
assert serialized_tree == '1,2,3,4,5,None,None'
deserialized_tree = deserialize(serialized_tree)
display_tree(deserialized_tree)
print('')

# test 1 # test 2 # test 3 # test 4