# [[tree|Tree]] [[serialize|Serialization]]
https://leetcode.com/problems/serialize-and-deserialize-binary-tree/
## [[bfs|BFS]]
Serialize level by level. Mark the children of leaves as `null`.
```python
def serialize(root):
if not root:
return ""
output = []
queue = deque([root])
while queue:
node = queue.popleft()
if node:
output.append(str(node.val))
queue.append(node.left)
queue.append(node.right)
else:
output.append('n')
return ','.join(output)
def deserialize(data):
if not data:
return None
nodes = data.split(',')
root = TreeNode(int(nodes[0]))
queue = deque([root])
index = 1
while queue and index < len(nodes):
node = queue.popleft()
if nodes[index] != 'n':
node.left = TreeNode(int(nodes[index]))
queue.append(node.left)
index += 1
if index < len(nodes) and nodes[index] != 'n':
node.right = TreeNode(int(nodes[index]))
queue.append(node.right)
index += 1
return root
```
A simpler `deserialize` version. Intuition: use `queue` to remember the parents to attach the new nodes to.
```python
def deserialize(self, data):
if not data:
return None
nodes = data.split(',')
root = TreeNode(int(nodes.pop(0)))
queue = [root]
while nodes:
parent = queue.pop(0)
left_val = nodes.pop(0) if nodes else 'n'
if left_val != 'n':
parent.left = TreeNode(int(left_val))
queue.append(parent.left)
if nodes:
right_val = nodes.pop(0)
if right_val != 'n':
parent.right = TreeNode(int(right_val))
queue.append(parent.right)
return root
```
## [[dfs|DFS]]
Can be preorder, inorder, or postorder. More natural compared to BFS when deserialize.
```python
def serialize(root):
def rserialize(root, string):
if root is None:
string += 'None,'
else:
string += str(root.val) + ','
string = rserialize(root.left, string)
string = rserialize(root.right, string)
return string
return rserialize(root, '')
```
```python
def deserialize(data):
def rdeserialize(l):
if l[0] == 'None':
l.pop(0)
return None
root = TreeNode(l.pop(0))
root.left = rdeserialize(l)
root.right = rdeserialize(l)
return root
data_list = data.split(',')
root = rdeserialize(data_list)
return root
```