Serialize and Deserialize Binary Tree

Problem: Serialize and Deserialize Binary Tree

We can use breadth-first search to get each level of the tree and append them together to serialize the tree. It's necessary to add dummy children to leaf nodes to make end of the path. During deserialize, we can also use BFS to extend path from root at each level.

Code in Python:

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

from collections import deque

class Codec:

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

        :type root: TreeNode
        :rtype: str
        """
        queue, res = deque([root]), ""
        while queue:
            node = queue.popleft()
            if node:
                res += str(node.val) + "/"
                queue.append(node.left)
                queue.append(node.right)
            else:
                res += "?/"
        return res


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

        :type data: str
        :rtype: TreeNode
        """
        _data = data.split("/")
        values = deque(_data[:len(_data)-1])
        if not values: return None
        if values[0] == "?": return None
        root = TreeNode(values.popleft())
        level = [root]
        while level:
            next = []
            for node in level:
                if values:
                    value = values.popleft()
                    if value != "?":
                        node.left = TreeNode(value)
                        next.append(node.left)
                if values:
                    value = values.popleft()
                    if value != "?":
                        node.right = TreeNode(value)
                        next.append(node.right)
            level = next
        return root


# Your Codec object will be instantiated and called as such:
# codec = Codec()
# codec.deserialize(codec.serialize(root))