# Python solution with detailed explanation

• Solution

Serialize and Deserialize Binary Tree https://leetcode.com/problems/serialize-and-deserialize-binary-tree/

Preorder & DFS

• Serialize using pre-order and represent null by "#"
• Deserialize by traversing the serialized tree and using recursion. O(N).
``````class Codec:
def preorder_serialize(self, root, result):
if root == None:
result.append("#")
else:
result.append(str(root.val))
self.preorder_serialize(root.left, result)
self.preorder_serialize(root.right, result)
return

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

:type root: TreeNode
:rtype: str
"""
result = []
self.preorder_serialize(root, result)
return ",".join(result)

def pre_order_deserialize(self, pre_order):
if pre_order[self.idx] == "#":
return None
else:
node = TreeNode(pre_order[self.idx])
self.idx += 1
node.left =  self.pre_order_deserialize(pre_order)
self.idx += 1
node.right =  self.pre_order_deserialize(pre_order)
return node

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

:type data: str
:rtype: TreeNode
"""
pre_order = data.split(",")
self.idx = 0
return self.pre_order_deserialize(pre_order)
``````

BFS

• Serialize the tree level by level using BFS. Typical BFS method to handle a binary tree. Use string n to represent null values. The string of the binary tree in the example will be "1 2 3 n n 4 5 n n n n ".
• Deserialize using queue and BFS variant. Assign left and right child for each not-null node, and add the not-null children to the queue, waiting to be handled later.
• Example, load the queue with TreeNode(1) and maintain a variable i which points to index location 1 in the serialized string.
• Now when we pop the queue and get Node(1), we check the index 1 and 2 for its left and right children. If any of them are non-null, we create them and attach them to Node(1) and then insert them back into the queue.
• https://discuss.leetcode.com/topic/31264/short-and-straight-forward-bfs-java-code-with-a-queue
``````from collections import deque
class Codec:
def serialize(self, root):
"""Encodes a tree to a single string.

:type root: TreeNode
:rtype: str
"""
q, result = deque(), []
q.append(root)
while len(q):
x = q.popleft()
if x == None:
result.append("#")
else:
result.append(str(x.val))
q.append(x.left)
q.append(x.right)
return ",".join(result)

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

:type data: str
:rtype: TreeNode
"""
data, q, idx = data.split(","), deque(), 0
if data[0] == "#":
return None
root = TreeNode(data[0])
q.append(root)
while len(q):
x = q.popleft()
x.left = TreeNode(data[idx+1]) if data[idx+1] != "#" else None
x.right = TreeNode(data[idx+2]) if data[idx+2] != "#" else None
if x.left:
q.append(x.left)
if x.right:
q.append(x.right)
idx += 2
return root
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.