# Daily Coding Problem Solution 3

Given the root to a binary tree, implement serialize(root), which serializes the tree into a string, and deserialize(s), which deserializes the string back into the tree.

For example, given the following Node class

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

The following test should pass:

``````node = Node('root', Node('left', Node('left.left')), Node('right'))
assert deserialize(serialize(node)).left.left.val == 'left.left'
``````

### 2 Internet Solutions

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

class Codec:

def serialize(self, root):
"""Encodes a tree to a single string.

:type root: TreeNode
:rtype: str
"""
if not root:
return ""

cur = root
stk = []
res = []

while cur or stk:
if cur:
res.append(str(cur.val))
stk.append(cur)
cur = cur.left
else:
res.append("#")
cur = stk.pop()
cur = cur.right
else:
res.append("#")

return " ".join(res)

def deserialize(self, data):
"""Decodes your encoded data to tree.

:type data: str
:rtype: TreeNode
"""
if len(data) == 0:
return None

strings = data.split(" ")

root = Node(strings[0])
cur = root
stk = []

for string in strings[1:]:
node = None
if string == "#":
node = None
else:
node = Node(string)

if cur:
cur.left = node
stk.append(cur)
cur = cur.left
else:
cur = stk.pop()
cur.right = node
cur = cur.right

return root

class Codec2:

def serialize(self, root):
"""Encodes a tree to a single string.

:type root: TreeNode
:rtype: str
"""
output = []

queue = deque([root])

while queue:
tmp = deque()

while queue:
node = queue.popleft()
if not node:
output.append('#')
else:
output.append(str(node.val))
tmp.append(node.left)
tmp.append(node.right)

queue = tmp

return ' '.join(output) if output[0] != '#' else ''

def deserialize(self, data):
"""Decodes your encoded data to tree.

:type data: str
:rtype: TreeNode
"""

if not data:
return None

data = data.split(' ')

root = Node(data[0])
i = 1

queue = deque([root])

while i < len(data):
tmp = deque()

while queue:
node = queue.popleft()

if data[i] == '#':
node.left = None
else:
node.left = Node(data[i])
tmp.append(node.left)

i += 1

if data[i] == '#':
node.right = None
else:
node.right = Node(data[i])
tmp.append(node.right)

i += 1

queue = tmp

return root

y = Codec()
y2 = Codec2()
node = Node('root', Node('left', Node('left.left')), Node('right'))
assert y.deserialize(y.serialize(node)).left.left.val == 'left.left'
assert y2.deserialize(y2.serialize(node)).left.left.val == 'left.left'
assert
``````